Skip to main content

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

Time: Fri 2024-03-15 11.15

Location: KTH 3418, Lindstedtsvägen 25 and Zoom

Video link: Meeting ID: 632 2469 3290

Participating: Guido Montúfar (UCLA and MPI Leipzig)

Export to calendar


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.