Back to Search
Start Over
An almost optimal approximation algorithm for monotone submodular multiple knapsack.
- Source :
-
Journal of Computer & System Sciences . May2022, Vol. 125, p149-165. 17p. - Publication Year :
- 2022
-
Abstract
- We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set I of items, each has a non-negative weight, and a set of bins of 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 packing of a subset of items A ⊆ I in the bins such that f (A) is maximized. Our main result is an almost optimal polynomial time (1 − e − 1 − ε) -approximation algorithm for the problem, for any ε > 0. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 125
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 154375516
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.11.005