Submodular function maximization via the multilinear relaxation and contention resolution schemes

Abstract

We consider the problem of maximizing a non-negative 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 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. © 2011 ACM.