Document Open Access Logo

The Online Simple Knapsack Problem with Reservation and Removability

Authors Elisabet Burjons , Matthias Gehnen , Henri Lotze , Daniel Mock , Peter Rossmanith

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.29.pdf
  • Filesize: 0.69 MB
  • 12 pages

Document Identifiers

Author Details

Elisabet Burjons
  • York University, Toronto, Canada
Matthias Gehnen
  • RWTH Aachen University, Germany
Henri Lotze
  • RWTH Aachen University, Germany
Daniel Mock
  • RWTH Aachen University, Germany
Peter Rossmanith
  • RWTH Aachen University, Germany

Cite As Get BibTex

Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith. The Online Simple Knapsack Problem with Reservation and Removability. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.29

Abstract

In the online simple knapsack problem, a knapsack of unit size 1 is given and an algorithm is tasked to fill it using a set of items that are revealed one after another. Each item must be accepted or rejected at the time they are presented, and these decisions are irrevocable. No prior knowledge about the set and sequence of items is given. The goal is then to maximize the sum of the sizes of all packed items compared to an optimal packing of all items of the sequence.
In this paper, we combine two existing variants of the problem that each extend the range of possible actions for a newly presented item by a new option. The first is removability, in which an item that was previously packed into the knapsack may be finally discarded at any point. The second is reservations, which allows the algorithm to delay the decision on accepting or rejecting a new item indefinitely for a proportional fee relative to the size of the given item.
If both removability and reservations are permitted, we show that the competitive ratio of the online simple knapsack problem rises depending on the relative reservation costs. As soon as any nonzero fee has to be paid for a reservation, no online algorithm can be better than 1.5-competitive. With rising reservation costs, this competitive ratio increases up to the golden ratio (ϕ ≈ 1.618) that is reached for relative reservation costs of 1-√5/3 ≈ 0.254. We provide a matching upper and lower bound for relative reservation costs up to this value. From this point onward, the tight bound by Iwama and Taketomi for the removable knapsack problem is the best possible competitive ratio, not using any reservations.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • online algorithm
  • knapsack
  • competitive ratio
  • reservation
  • preemption

Metrics

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

References

  1. Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, and Avi Wigderson. On the power of randomization in online algorithms (extended abstract). In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 379-386. ACM, 1990. URL: https://doi.org/10.1145/100216.100268.
  2. Hans-Joachim Böckenhauer, Elisabet Burjons, Juraj Hromkovic, Henri Lotze, and Peter Rossmanith. Online simple knapsack with reservation costs. In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 16:1-16:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.16.
  3. Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, and Peter Rossmanith. The online knapsack problem: Advice and randomization. Theor. Comput. Sci., 527:61-72, 2014. URL: https://doi.org/10.1016/j.tcs.2014.01.027.
  4. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Google Scholar
  5. Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith. The secretary problem with reservation costs. In Chi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, and Chia-Wei Lee, editors, Computing and Combinatorics - 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24-26, 2021, Proceedings, volume 13025 of Lecture Notes in Computer Science, pages 553-564. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-89543-3_46.
  6. Elisabet Burjons, Juraj Hromkovic, Rastislav Královic, Richard Královic, Xavier Muñoz, and Walter Unger. Online graph coloring against a randomized adversary. Int. J. Found. Comput. Sci., 29(4):551-569, 2018. URL: https://doi.org/10.1142/S0129054118410058.
  7. Stefan Dobrev, Rastislav Královic, and Dana Pardubská. Measuring the problem-relevant information in input. RAIRO Theor. Informatics Appl., 43(3):585-613, 2009. URL: https://doi.org/10.1051/ita/2009012.
  8. Xin Han, Yasushi Kawase, and Kazuhisa Makino. Online unweighted knapsack problem with removal cost. Algorithmica, 70(1):76-91, 2014. URL: https://doi.org/10.1007/s00453-013-9822-z.
  9. Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku. Online knapsack problems with a resource buffer. In Pinyan Lu and Guochuan Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, volume 149 of LIPIcs, pages 28:1-28:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.28.
  10. Juraj Hromkovic, Rastislav Královic, and Richard Královic. Information complexity of online problems. In Petr Hlinený and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6281 of Lecture Notes in Computer Science, pages 24-36. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15155-2_3.
  11. Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM, 22(4):463-468, 1975. URL: https://doi.org/10.1145/321906.321909.
  12. Kazuo Iwama and Shiro Taketomi. Removable online knapsack problems. In Peter Widmayer, Francisco Triguero Ruiz, Rafael Morales Bueno, Matthew Hennessy, Stephan J. Eidenbenz, and Ricardo Conejo, editors, Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings, volume 2380 of Lecture Notes in Computer Science, pages 293-305. Springer, 2002. URL: https://doi.org/10.1007/3-540-45465-9_26.
  13. Kazuo Iwama and Guochuan Zhang. Online knapsack with resource augmentation. Inf. Process. Lett., 110(22):1016-1020, 2010. URL: https://doi.org/10.1016/j.ipl.2010.08.013.
  14. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  15. Dennis Komm. An Introduction to Online Computation - Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-42749-2.
  16. Elias Koutsoupias and Christos H. Papadimitriou. Beyond competitive analysis. SIAM J. Comput., 30(1):300-317, 2000. URL: https://doi.org/10.1137/S0097539796299540.
  17. Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Math. Program., 68:73-104, 1995. URL: https://doi.org/10.1007/BF01585758.
  18. Prabhakar Raghavan. A statistical adversary for on-line algorithms. In Lyle A. McGeoch and Daniel Dominic Sleator, editors, On-Line Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, February 11-13, 1991, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 79-84. DIMACS/AMS, 1991. URL: https://doi.org/10.1090/dimacs/007/05.
  19. Daniel Dominic Sleator and Robert Endre Tarjan. Amortized efficiency of list update rules. In Richard A. DeMillo, editor, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 488-492. ACM, 1984. URL: https://doi.org/10.1145/800057.808718.
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