Document Open Access Logo

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Authors Alexandra Lassota, Aleksander Łukasiewicz , Adam Polak

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.87.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

Alexandra Lassota
  • EPFL, Lausanne, Switzerland
Aleksander Łukasiewicz
  • University of Wrocław, Poland
Adam Polak
  • EPFL, Lausanne, Switzerland

Funding

  • Lassota, Alexandra: Swiss National Science Foundation project Lattice Algorithms and Integer Programming (185030).
  • Łukasiewicz, Aleksander: Polish National Science Centre grant 2019/33/B/ST6/00298.
  • Polak, Adam: Swiss National Science Foundation project Lattice Algorithms and Integer Programming (185030).

Cite As Get BibTex

Alexandra Lassota, Aleksander Łukasiewicz, and Adam Polak. Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.87

Abstract

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. Our algorithm is actually designed to work for a more general Vector Bin Packing problem, in which items are multidimensional vectors. We improve over the previous fastest O^*(k! ⋅ 4^k) time algorithm.
Our algorithm works by reducing the problem to finding an exact weight perfect matching in a (multi-)graph with O^*(2^k) edges, whose weights are integers of the order of O^*(2^k). To solve the matching problem in the desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani algorithm with only a linear dependence on the edge weights and the number of edges - which may be of independent interest.
Moreover, we give a tight lower bound, under the Strong Exponential Time Hypothesis (SETH), showing that the constant 2 in the base of the exponent cannot be further improved for Vector Bin Packing.
Our techniques also lead to improved algorithms for Vector Multiple Knapsack, Vector Bin Covering, and Perfect Matching with Hitting Constraints.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Bin Packing
  • Vector Bin Packing
  • Parameterized Complexity
  • Matching

Metrics

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

Related Versions

References

  1. Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002. URL: https://doi.org/10.1007/s00453-001-0116-5.
  2. Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, and Malte Skambath. Solving Packing Problems with Few Small Items Using Rainbow Matchings. In MFCS, volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1-11:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.11.
  3. Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, and Malte Skambath. Solving Packing Problems with Few Small Items Using Rainbow Matchings. CoRR, abs/2007.02660, 2020. URL: http://arxiv.org/abs/2007.02660.
  4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  5. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  6. Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In IWPEC, volume 3162 of Lecture Notes in Computer Science, pages 162-173. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-28639-4_15.
  7. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  8. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In FOCS, pages 653-663. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/SFCS.1998.743516.
  9. Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for scheduling and packing problems. SIAM Journal on Discrete Mathematics, 30(1):343-366, 2016. URL: https://doi.org/10.1137/140952636.
  10. Meena Mahajan, P. R. Subramanya, and V. Vinay. A combinatorial algorithm for Pfaffians. In COCOON, COCOON'99, pages 134-143, Berlin, Heidelberg, 1999. Springer-Verlag. URL: https://doi.org/10.1007/3-540-48686-0_13.
  11. Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In STACS, volume 25 of LIPIcs, pages 542-553. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.542.
  12. Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, March 1987. URL: https://doi.org/10.1007/BF02579206.
  13. Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, and Karol Wegrzycki. A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatorics. In SODA, pages 1682-1701. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.102.
  14. Rolf Niedermeier and Peter Rossmanith. An efficient fixed-parameter algorithm for 3-hitting set. Journal of Discrete Algorithms, 1(1):89-102, 2003. URL: https://doi.org/10.1016/S1570-8667(03)00009-1.
  15. Christos H Papadimitriou and Mihalis Yannakakis. The complexity of restricted spanning tree problems. Journal of the ACM, 29(2):285-309, 1982. URL: https://doi.org/10.1145/322307.322309.
  16. Igor Razgon and Barry O'Sullivan. Almost 2-SAT is fixed-parameter tractable (extended abstract). In ICALP, volume 5125 of Lecture Notes in Computer Science, pages 551-562. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_45.
  17. Günter Rote. Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches. In Computational Discrete Mathematics: advanced lectures, pages 119-135. Springer-Verlag, 2001. URL: https://doi.org/10.1007/3-540-45506-X_9.
  18. Ola Svensson and Jakub Tarnawski. The matching problem in general graphs is in quasi-NC. In FOCS, pages 696-707. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.70.
  19. Anna Urbańska. Faster combinatorial algorithms for determinant and Pfaffian. In Algorithms and Computation, 18th International Symposium, ISAAC 2007, pages 599-608. Springer Berlin Heidelberg, 2007. URL: https://doi.org/10.1007/978-3-540-77120-3_52.
  20. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In ICM, pages 3447-3487. World Scientific, 2018. URL: https://doi.org/10.1142/9789813272880_0188.
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 About DROPS Imprint Privacy Contact