Document Open Access Logo

An Optimal Algorithm for Online Multiple Knapsack

Authors Marcin Bienkowski , Maciej Pacut , Krzysztof Piecuch

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.13.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

Marcin Bienkowski
  • Institute of Computer Science, University of Wrocław, Poland
Maciej Pacut
  • Faculty of Computer Science, University of Vienna, Austria
Krzysztof Piecuch
  • Institute of Computer Science, University of Wrocław, Poland

Funding

Research supported by Polish National Science Centre grants 2016/22/E/ST6/00499 and 2016/23/N/ST6/03412.

Cite AsGet BibTex

Marcin Bienkowski, Maciej Pacut, and Krzysztof Piecuch. An Optimal Algorithm for Online Multiple Knapsack. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.13

Abstract

In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of n bins (knapsacks) of equal size. The gain of an algorithm is equal to the sum of sizes of accepted items and the goal is to maximize the total gain. So far, for this natural problem, the best solution was the 0.5-competitive algorithm FirstFit (the result holds for any n ≥ 2). We present the first algorithm that beats this ratio, achieving the competitive ratio of 1/(1+ln(2))-O(1/n) ≈ 0.5906 - O(1/n). Our algorithm is deterministic and optimal up to lower-order terms, as the upper bound of 1/(1+ln(2)) for randomized solutions was given previously by Cygan et al. [TOCS 2016].

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online knapsack
  • multiple knapsacks
  • bin packing
  • competitive analysis

Metrics

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

Related Versions

References

  1. Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and GAP in the random order model. In Proc. 22nd Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 22:1-22:23, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.22.
  2. Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen, and Leah Epstein. Fair versus unrestricted bin packing. Algorithmica, 34(2):181-196, 2002. URL: https://doi.org/10.1007/s00453-002-0965-6.
  3. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Proc. 11th Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 16-28, 2007. URL: https://doi.org/10.1007/978-3-540-74208-1_2.
  4. Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, and Peter Rossmanith. The online knapsack problem: Advice and randomization. Theoretical Computer Science, 527:61-72, 2014. URL: https://doi.org/10.1016/j.tcs.2014.01.027.
  5. Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen. The competitive ratio for on-line dual bin packing with restricted input sequences. Nordic Journal of Computing, 8(4):463-472, 2001. Google Scholar
  6. Chandra Chekuri and Sanjeev Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 35(3):713-728, 2005. URL: https://doi.org/10.1137/S0097539700382820.
  7. Marek Cygan, Łukasz Jeż, and Jirí Sgall. Online knapsack revisited. Theory of Computing Systems, 58(1):153-190, 2016. URL: https://doi.org/10.1007/s00224-014-9566-4.
  8. Xin Han, Yasushi Kawase, and Kazuhisa Makino. Randomized algorithms for online knapsack problems. Theoretical Computer Science, 562:395-405, 2015. URL: https://doi.org/10.1016/j.tcs.2014.10.017.
  9. Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku. Online knapsack problems with a resource buffer. In Proc. 30th Int. Symp. on Algorithms and Computation (ISAAC), pages 28:1-28:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.28.
  10. Kazuo Iwama and Shiro Taketomi. Removable online knapsack problems. In Proc. 29th Int. Colloq. on Automata, Languages and Programming (ICALP), pages 293-305, 2002. URL: https://doi.org/10.1007/3-540-45465-9_26.
  11. Kazuo Iwama and Guochuan Zhang. Online knapsack with resource augmentation. Information Processing Letters, 110(22):1016-1020, 2010. URL: https://doi.org/10.1016/j.ipl.2010.08.013.
  12. Hans Kellerer. A polynomial time approximation scheme for the multiple knapsack problem. In Proc. 3rd Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 51-62, 1999. URL: https://doi.org/10.1007/978-3-540-48413-4_6.
  13. Hans Kellerer. Knapsack. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 1048-1051. Springer, 2016. Google Scholar
  14. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer, 2004. Google Scholar
  15. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing LPs in the random-order model. SIAM Journal on Computing, 47(5):1939-1964, 2018. URL: https://doi.org/10.1137/15M1033708.
  16. Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68:73-104, 1995. URL: https://doi.org/10.1007/BF01585758.
  17. John Noga and Veerawan Sarbua. An online partially fractional knapsack problem. In 8th Int. Symp. on Parallel Architectures, Algorithms, and Networks (ISPAN), pages 108-112, 2005. URL: https://doi.org/10.1109/ISPAN.2005.19.
  18. David Pisinger. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research, 114(3):528-541, 1999. URL: https://doi.org/10.1016/S0377-2217(98)00120-9.
  19. Rahul Vaze. Online knapsack problem and budgeted truthful bipartite matching. In Proc. 36th IEEE Int. Conf. on Computer Communications (INFOCOM), pages 1-9, 2017. URL: https://doi.org/10.1109/INFOCOM.2017.8057223.
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