TY - JOUR
T1 - Submodular function maximization via the multilinear relaxation and contention resolution schemes
AU - Chekuri, Chandra
AU - Vondrák, Jan
AU - Zenklusen, Rico
N1 - Publisher Copyright:
© 2014 Society for Industrial and Applied Mathematics
PY - 2014
Y1 - 2014
N2 - We consider the problem of maximizing a nonnegative submodular set function f : 2N → ℝ+ 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 nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension F of f over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, 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 a downward-closed polytope P described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap 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.
AB - We consider the problem of maximizing a nonnegative submodular set function f : 2N → ℝ+ 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 nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension F of f over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, 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 a downward-closed polytope P described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap 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.
KW - Approximation algorithms
KW - Contention resolution
KW - Randomized algorithms
KW - Submodular function maximization
UR - http://www.scopus.com/inward/record.url?scp=84920742613&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84920742613&partnerID=8YFLogxK
U2 - 10.1137/110839655
DO - 10.1137/110839655
M3 - Article
AN - SCOPUS:84920742613
SN - 0097-5397
VL - 43
SP - 1831
EP - 1879
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 6
ER -