Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: A-Approximation for the Monotone Submodular Multiple Knapsack Problem
event speaker icon
Yaron Fairstein (CS, Technion)
event date icon
Wednesday, 09.12.2020, 12:30
event location icon
Zoom, Meeting ID: 954 7347 4134, Password: 5-digit Technion Zip Code
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.