文章基本信息

标题：A (1-e^{-1}-Îµ)-Approximation for the Monotone Submodular Multiple Knapsack Problem
本地全文：下载
作者：Yaron Fairstein ; Ariel Kulik ; Joseph 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：44:1-44:19
DOI：10.4230/LIPIcs.ESA.2020.44
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 having arbitrary capacities. 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 âS I and a packing of these 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.
关键词：Sumodular Optimization; Multiple Knapsack; Randomized Rounding