Constrained Submodular Maximization via Greedy Local Search Baruch Schieber, IBM AI Research
We present a simple combinatorial (1/2)(1- 1/(e^2))-approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint. This classic problem is known to be hard to approximate within factor better than 1 - 1/e. We extend the algorithm to yield (1/k)(1- 1/(e^k)) approximation for submodular maximization subject to a single knapsack and k-1 matroid constraints, for any fixed k>1. Our algorithms, which combine the greedy algorithm of [Khuller, Moss and Naor, 1999] and [Sviridenko, 2004] with local search, show the power of this natural framework in submodular maximization with combined constraints. This is joint work with Kanthi Sarpatwar and Hadas Shachnai.