HEXAGONbeta

The Exact One-Half Threshold for Arbitrary-Capacity Bottleneck Multiple Subset Sum

Primarily AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithmscs.CC — Computational Complexitymath.OC — Optimization and Control

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Nov 04, 2026 / CC BY 4.0

Abstract

In bottleneck multiple subset sum, items with weights are packed into knapsacks with capacities, possibly leaving items unpacked, so as to maximize the minimum load. For identical capacities the best possible approximation ratio is 2/32/3, and Chen et al.\ asked whether 2/32/3 is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a 1/21/2-approximation using O(nlog⁡(n+1)+mlog⁡(m+1))O(n\log(n+1)+m\log(m+1)) arithmetic and comparison operations for nn items and mm knapsacks, and prove that no fixed ratio above 1/21/2 is achievable unless P=NP\mathsf P=\mathsf{NP}. We also give a short proof of the classical 1/21/2 guarantee of Friesen and Langston for unit profits.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.

Tools used

Bolzano team
Bolzano

References

  1. A. Caprara, H. Kellerer, and U. Pferschy, The multiple subset sum problem, SIAM Journal on Optimization 11 (2000), no. 2, 308--319, doi:10.1137/S1052623498348481 (https://doi.org/10.1137/S1052623498348481).DOI
  2. A. Caprara, H. Kellerer, and U. Pferschy, A PTAS for the multiple subset sum problem with different knapsack capacities, Information Processing Letters 73 (2000), no. 3--4, 111--118, doi:10.1016/S0020-0190(00)00010-7 (https://doi.org/10.1016/S0020-0190(00)00010-7).DOI
  3. L. Chen, T. Hu, Y. Mao, Y. Chen, L. Mei, A. Zhang, G. Chen, and G. Zhang, Near-tight approximation algorithms for bottleneck multiple knapsack problems, in S. Bhattacharya, D. Nanongkai, M. Benedikt, and G. Puppis (eds.), 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) , LIPIcs 374, 60:1--60:19, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ICALP.2026.60 (https://doi.org/10.4230/LIPIcs.ICALP.2026.60); full version arXiv:2605.05233.arXivDOI
  4. D. K. Friesen and M. A. Langston, Bin packing: On optimizing the number of pieces packed, BIT Numerical Mathematics 27 (1987), no. 2, 148--156, doi:10.1007/BF01934179 (https://doi.org/10.1007/BF01934179).DOI
  5. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, San Francisco, 1979; see Appendix A, Numerical Matching with Target Sums, Problem SP17, p. 224.
  6. B. L. Deuermeyer, D. K. Friesen, and M. A. Langston. Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J. Algebraic Discrete Methods , 3(2):190--196, 1982. https://doi.org/10.1137/0603019.DOI
  7. G. J. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. , 20(4):149--154, 1997. https://doi.org/10.1016/S0167-6377(96)00055-7.DOI
  8. S. F. Assmann, D. S. Johnson, D. J. Kleitman, and J. Y.-T. Leung. On a dual version of the one-dimensional bin packing problem. J. Algorithms , 5(4):502--525, 1984. https://doi.org/10.1016/0196-6774(84)90004-X.DOI
  9. K. Jansen and R. Solis-Oba. An asymptotic fully polynomial time approximation scheme for bin covering. Theoret. Comput. Sci. , 306(1--3):543--551, 2003. https://doi.org/10.1016/S0304-3975(03)00363-3.DOI
  10. C. Chekuri and S. Khanna, A polynomial time approximation scheme for the multiple knapsack problem, SIAM Journal on Computing 35 (2006), no. 3, 713--728, doi:10.1137/S0097539700382820 (https://doi.org/10.1137/S0097539700382820).DOI
Show all 13 referencesShow fewer references
  1. N. Bansal and M. Sviridenko, The Santa Claus problem, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006) , 31--40, doi:10.1145/1132516.1132522 (https://doi.org/10.1145/1132516.1132522).DOI
  2. H. Hummel, Maximin shares in hereditary set systems, ACM Transactions on Economics and Computation 13 (2025), no. 3, Article 12, 1--33, doi:10.1145/3727149 (https://doi.org/10.1145/3727149); arXiv:2404.11582 (https://arxiv.org/abs/2404.11582).arXivDOI
  3. L. Rohwedder, A. Rouhani, and L. Wennmann, Cost preserving dependent rounding for allocation problems, in 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , LIPIcs 334, 127:1--127:20, doi:10.4230/LIPIcs.ICALP.2025.127 (https://doi.org/10.4230/LIPIcs.ICALP.2025.127); arXiv:2502.08267v2 (https://arxiv.org/abs/2502.08267v2).arXivDOI

Version history

  1. v1 · 9 pagesSubmitted by Václav RozhoňInitial depositCurrentNov 03, 2026