Document Open Access Logo

Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping

Authors Yaron Fairstein, Ariel Kulik, Hadas Shachnai

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.41.pdf
  • Filesize: 0.75 MB
  • 16 pages

Document Identifiers

Author Details

Yaron Fairstein
  • Computer Science Department, Technion, Haifa, Israel
Ariel Kulik
  • Computer Science Department, Technion, Haifa, Israel
Hadas Shachnai
  • Computer Science Department, Technion, Haifa, Israel

Cite AsGet BibTex

Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.41

Abstract

A multiple knapsack constraint over a set of items is defined by a set of bins of arbitrary capacities, and a weight for each of the items. An assignment for the constraint is an allocation of subsets of items to the bins which adheres to bin capacities. In this paper we present a unified algorithm that yields efficient approximations for a wide class of submodular and modular optimization problems involving multiple knapsack constraints. One notable example is a polynomial time approximation scheme for Multiple-Choice Multiple Knapsack, improving upon the best known ratio of 2. Another example is Non-monotone Submodular Multiple Knapsack, for which we obtain a (0.385-ε)-approximation, matching the best known ratio for a single knapsack constraint. The robustness of our algorithm is achieved by applying a novel fractional variant of the classical linear grouping technique, which is of independent interest.

Subject Classification

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

Metrics

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

Related Versions

References

  1. Alexander A Ageev and Maxim I Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8(3):307-328, 2004. Google Scholar
  2. Evripidis Bampis, Bruno Escoffier, and Alexandre Teiller. Multistage Knapsack. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), pages 22:1-22:14, 2019. Google Scholar
  3. Nikhil Bansal, Marek Eliáš, and Arindam Khan. Improved approximation for vector bin packing. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1561-1579, 2016. Google Scholar
  4. Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a nonsymmetric technique. Mathematics of Operations Research, 44(3):988-1005, 2019. Google Scholar
  5. 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 (SODA), pages 1433-1452. SIAM, 2014. Google Scholar
  6. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. In Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pages 182-196, 2007. Google Scholar
  7. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740-1766, 2011. URL: https://doi.org/10.1137/080733991.
  8. Chandra Chekuri and Sanjeev Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput., 35(3):713-728, 2005. URL: https://doi.org/10.1137/S0097539700382820.
  9. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), page 575–584, 2010. Google Scholar
  10. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 1080-1097, 2011. Google Scholar
  11. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43(6):1831-1879, 2014. Google Scholar
  12. Reuven Cohen and Guy Grebla. Efficient allocation of periodic feedback channels in broadband wireless networks. IEEE/ACM Transactions on Networking, 23(2):426-436, 2014. Google Scholar
  13. 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
  14. Yaron Fairstein, Ariel Kulik, Joseph Naor, and Danny Raz. General knapsack problems in a dynamic setting. To appear in APPROX, 2021. Google Scholar
  15. 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), pages 44:1-44:19, 2020. Google Scholar
  16. Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Modular and submodular optimization with multiple knapsack constraints via fractional grouping, 2020. URL: http://arxiv.org/abs/2007.10470.
  17. Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Tight approximations for modular and submodular optimization with d-resource multiple knapsack constraints, 2020. (second version). URL: http://arxiv.org/abs/2007.10470v2.
  18. U. Feige and M. Goemans. Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems, ISTCS '95, pages 182-189, 1995. Google Scholar
  19. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998. Google Scholar
  20. 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 (FOCS), pages 570-579, 2011. Google Scholar
  21. Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum separable assignment problems. Mathematics of Operations Research, 36(3):416-431, 2011. Google Scholar
  22. Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 1098-1116, 2011. Google Scholar
  23. Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem. SIAM J. Comput., 39(4):1392-1412, 2010. Google Scholar
  24. Klaus Jansen. A fast approximation scheme for the multiple knapsack problem. In SOFSEM'12, pages 313-324, 2012. URL: https://doi.org/10.1007/978-3-642-27660-6_26.
  25. Narendra Karmarkar and Richard M Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 312-320, 1982. Google Scholar
  26. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004. Google Scholar
  27. Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999. Google Scholar
  28. Ariel Kulik and Hadas Shachnai. There is no EPTAS for two-dimensional knapsack. Information Processing Letters, 110(16):707-710, 2010. Google Scholar
  29. Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res., 38(4):729-739, 2013. URL: https://doi.org/10.1287/moor.2013.0592.
  30. 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
  31. S. Martello and P. Toth. Knapsack problems: algorithms and computer implementations. Wiley-Interscience series in discrete mathematics and optimiza tion, 1990. Google Scholar
  32. G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177-188, 1978. Google Scholar
  33. Thomas Rothvoß. Approximating bin packing within o (log opt* log log opt) bins. In IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 20-29, 2013. Google Scholar
  34. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  35. Xiaoming Sun, Jialin Zhang, and Zhijie Zhang. Tight algorithms for the submodular multiple knapsack problem. arXiv preprint arXiv:2003.11450, 2020. Google Scholar
  36. 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
  37. Deepak S Turaga, Krishna Ratakonda, and Junwen Lai. QoS support for media broadcast in a services oriented architecture. In 2006 IEEE International Conference on Services Computing (SCC'06), pages 127-134, 2006. Google Scholar
  38. Hien Nguyen Van, Frédéric Dang Tran, and Jean-Marc Menaud. Performance and power management for cloud infrastructures. In IEEE 3rd international Conference on Cloud Computing (CLOUD), pages 329-336. IEEE, 2010. Google Scholar
  39. Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. Google Scholar
  40. Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265-304, 2013. Google Scholar
  41. Quanqing Xu, Khin Mi Mi Aung, Yongqing Zhu, and Khai Leong Yong. A blockchain-based storage system for data analytics in the internet of things. In New Advances in the Internet of Things, pages 119-138. Springer, 2018. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact