Talk - Baruch Schieber - IBM AI Research

02.01.2018 16:00 to 17:00
4172 AVW Bldg.

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.