Supermodular Rank: Set Function Decomposition and Optimization
The paper introduces supermodular rank, a measure of how complex a function is by finding the minimum number of supermodular functions needed to sum up to it. This rank is then used to develop algorithms that break down optimization problems involving set functions into smaller, manageable subproblems. This decomposition method improves the approximation guarantees for maximizing monotone set functions and minimizing ratios.