Supermodular Rank: Set Function Decomposition and Optimization
Rishi Sonthalia Anna Seigal Guido Montufar
We define the supermodular rank of a function on a lattice. This is the
smallest number of terms needed to decompose it into a sum of supermodular
functions. The supermodular summands are defined with respect to different
partial orders. We characterize the maximum possible value of the supermodular
rank and describe the functions with fixed supermodular rank. We analogously
define the submodular rank. We use submodular decompositions to optimize set
functions. Given a bound on the submodular rank of a set function, we formulate
an algorithm that splits an optimization problem into submodular subproblems.
We show that this method improves the approximation ratio guarantees of several
algorithms for monotone set function maximization and ratio of set functions
minimization, at a computation overhead that depends on the submodular rank.