Guido Montúfar: Supermodular Rank: Set Function Decomposition and Optimization

Abstract

We define the supermodular rank of a set function. 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. This is joint work with Rishi Sonthalia and Anna Seigal.