Constrained Submodular Maximization via Greedy Local Search

Baruch Schieber
IBM AI Research
02.01.2018 16:00 to 17:00
AVW 4172

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.