Submodular function maximization via the multilinear relaxation and contention resolution schemes

By Chandra Chekuri, Jan Vondr'ak, Rico Zenklusen. 2011

394 citations recorded by the source corpus.

We consider the problem of maximizing a non-negative submodular set function f:2N -> RR+ over a ground set N subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular when f may be a non-monotone function. Our algorithms are based on (approximately) solving the multilinear extension F of f [5] over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully in some settings [6, 22, 24, 13, 3], it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over an arbitrary down-closed polytope P that has an efficient separation oracle. Previously this was known only for monotone functions [36]. For non-monotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints [24] or a matroid polytope [37,30]. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is non-monotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via LP duality we show that a contention resolution scheme for a constraint is related to the correlation gap [1] of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, methodology): “[47] showed that even nonmonotone submodular functions can be approximately maximized in polynomial time using a local search algorithm, and a growing body of research has focused on extending this result in a variety of ways [25, 48, 49, 56, 90, 153].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “The multi-linear extension is neither convex nor concave but has marginal convexity properties that may be used for the design and analysis of algorithms for maximization problems [42, 68].”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “Following [21], we now define a surrogate function F̃ ⇤.”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, neutral): “[5] define a contention resolution rounding scheme which allows one to obtain approximations for different combinations of constraints.”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, background): “…line of research has lead to the development of algorithms to handle non-monotone submodular objectives and/or more complicated constraints (see, e.g., Buchbinder and Feldman [2016], Chekuri et al. [2014], Ene and Nguyen [2016], Feldman et al. [2017], Lee et al. [2010], Sviridenko [2004]).”
Submodular Function Maximization (2014, background): “Most recently, Chekuri et al. (2011) show how the factor 0 .”
Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, background): “In later work [8, 7], they developed the notion of a contention resolution scheme, which gives a unified treatment for a variety of constraints, and allows rounding approaches for the continuous greedy algorithm to be composed in order to solve submodular maximization problems under combinations of ”
Fast algorithms for maximizing submodular functions (2014, methodology): “Extensions and generalizations to nonmonotone submodular functions have been developed in [7, 25, 34, 26, 16, 13, 9, 10, 3, 1].”