Document Open Access Logo

A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem

Authors Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, Hadas Shachnai

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2020.44.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • Sumodular Optimization
  • Multiple Knapsack
  • Randomized Rounding

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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 ⊆ 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.

Cite As Get BibTex

Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, and Hadas Shachnai. A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.44

Author Details

Yaron Fairstein
  • Computer Science Department, Technion, Haifa, Israel
Ariel Kulik
  • Computer Science Department, Technion, Haifa, Israel
Joseph (Seffi) Naor
  • Computer Science Department, Technion, Haifa, Israel
Danny Raz
  • Computer Science Department, Technion, Haifa, Israel
Hadas Shachnai
  • Computer Science Department, Technion, Haifa, Israel

Funding

  • Naor, Joseph (Seffi): {This research was supported in part by US-Israel BSF grant 2018352 and by ISF grant 2233/19 (2027511).}

References

  1. Niv Buchbinder and Moran Feldman. Submodular functions maximization problems. Handbook of Approximation Algorithms and Metaheuristics, 1:753-788, 2017. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  6. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding for matroid polytopes and applications. arXiv preprint, 2009. URL: http://arxiv.org/abs/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. Google Scholar
  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. Google Scholar
  9. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  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. Google Scholar
  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. Google Scholar
  12. Moran Feldman and Seffi Naor. Maximization problems with submodular objective functions. PhD thesis, Computer Science Department, Technion, 2013. Google Scholar
  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. Google Scholar
  14. Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 39(4):1392-1412, 2010. Google Scholar
  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. Google Scholar
  16. Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  20. Xiaoming Sun, Jialin Zhang, and Zhijie Zhang. Tight algorithms for the submodular multiple knapsack problem. arXiv preprint, 2020. URL: http://arxiv.org/abs/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. Google Scholar
  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. Google Scholar
  23. Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265-304, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact