The Taub Faculty of Computer Science Events and Talks

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint (SMKP). The input is a set I of items, each associated with a non-negative weight, and a set of bins, each having a capacity. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a subset of items A⊆I and a packing of the items in the bins, such that f(A) is maximized. SMKP is a natural extension of both Multiple Knapsack and the problem of monotone submodular maximization subject to a knapsack constraint. Our main result is a nearly optimal polynomial time (1−e–1–ε)-approximation algorithm for the problem, for any ε>0. Our algorithm relies on a refined analysis of techniques for constrained submodular optimization combined with sophisticated application of tools used in the development of approximation schemes for packing problems. Joint work with Ariel Kulik, Seffi Naor, Danny Raz, and Hadas Shachnai. More details.