A \((1-e^{-1}-\varepsilon)\)-approximation for the monotone submodular multiple knapsack problem. (English) Zbl 07651183
Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 44, 19 p. (2020).
Summary: 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 nonnegative weight, and a set of bins having arbitrary capacities. Also, we are given a submodular, monotone and nonnegative function \(f\) over subsets of the items. The objective is to find a subset of items \(A\subseteq 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}-\varepsilon)\)-approximation algorithm for the problem, for any \(\varepsilon>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.
For the entire collection see [Zbl 1445.68017].
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}-\varepsilon)\)-approximation algorithm for the problem, for any \(\varepsilon>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.
For the entire collection see [Zbl 1445.68017].
MSC:
| 68Wxx | Algorithms in computer science |
References:
| [1] | Niv Buchbinder and Moran Feldman. Submodular functions maximization problems. Handbook of Approximation Algorithms and Metaheuristics, 1:753-788, 2017. |
| [2] | Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1433-1452. SIAM, 2014. · Zbl 1423.90212 |
| [3] | Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 182-196. Springer, 2007. · Zbl 1136.90449 |
| [4] | Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740-1766, 2011. · Zbl 1234.68459 |
| [5] | Chandra Chekuri and Sanjeev Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 35(3):713-728, 2005. · Zbl 1095.68035 |
| [6] | Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding for matroid polytopes and applications. arXiv preprint, 2009. arXiv:0909.4348. |
| [7] | Chandra Chekuri, Jan Vondrak, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 575-584. IEEE, 2010. |
| [8] | W Fernandez De La Vega and George S. Lueker. Bin packing can be solved within 1+ ε in linear time. Combinatorica, 1(4):349-355, 1981. · Zbl 0485.68057 |
| [9] | Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. · Zbl 1065.68573 |
| [10] | Uriel Feige and Michel Goemans. Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pages 182-189. IEEE, 1995. |
| [11] | Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 570-579. IEEE, 2011. · Zbl 1292.90248 |
| [12] | Moran Feldman and Seffi Naor. Maximization problems with submodular objective functions. PhD thesis, Computer Science Department, Technion, 2013. |
| [13] | Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM), 53(3):324-360, 2006. · Zbl 1312.68233 |
| [14] | Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 39(4):1392-1412, 2010. · Zbl 1211.68276 |
| [15] | Klaus Jansen. A fast approximation scheme for the multiple knapsack problem. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 313-324. Springer, 2012. · Zbl 1302.90183 |
| [16] | Samir Khuller, Anna Moss, and Joseph (Seffi) Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999. 44:17 · Zbl 1002.68203 |
| [17] | Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Mathematics of Operations Research, 38(4):729-739, 2013. · Zbl 1291.90205 |
| [18] | Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics, 23(4):2053-2078, 2010. · Zbl 1207.68445 |
| [19] | George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177-188, 1978. · Zbl 0395.90072 |
| [20] | Xiaoming Sun, Jialin Zhang, and Zhijie Zhang. Tight algorithms for the submodular multiple knapsack problem. arXiv preprint, 2020. arXiv:2003.11450. |
| [21] | Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41-43, 2004. · Zbl 1056.90124 |
| [22] | Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67-74, 2008. · Zbl 1231.91094 |
| [23] | Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265-304, 2013. · Zbl 1292.90261 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
