New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Local Search Algorithms for Submodular Maximization

SpeakerMaxim Sviridenko

We study the problem of maximizing a submodular function over the intersection of k matroids (for a constant k>=2). This is a fundamental optimization problem which generalizes the problem of maximum-weight independent set in the intersection of k+1 matroids (and hence also (k+1)-dimensional matching), maximizing entropy, coverage, or cut-type functions under k matroid constraints, and other problems. It is also contains scheduling on parallel machines with profit maximization (as opposed to cost or running time minimization). Our main result is that for any k>= 2 and any epsilon>0, there is a natural local-search algorithm which has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves a 1/(k+1)-approximation of Nemhauser, Wolsey and Fisher [1978]. For maximizing a linear function over k matroids, we obtain a 1/(k-1+epsilon)-approximation, improving a previously known 1/k-approximation. Our analysis can be applied even to general non-monotone submodular maximization subject to k matroid constraints. We show that in this case the approximation guarantee of our algorithm is 1/(k+1+1/(k-1)+epsilon), improving the previously known factor of 1/(k+2+1/k+\varepsilon).