Online Knapsack Problems with a Resource Buffer

Authors Xin Han, Yasushi Kawase, Kazuhisa Makino, Haruki Yokomaku



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.28.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Xin Han
  • Dalian University of Technology, Dalian, China
Yasushi Kawase
  • Tokyo Institute of Technology, Tokyo, Japan
Kazuhisa Makino
  • Kyoto University, Kyoto, Japan
Haruki Yokomaku
  • NTT DATA Mathematical Systems, Tokyo, Japan

Cite AsGet BibTex

Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku. Online Knapsack Problems with a Resource Buffer. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.28

Abstract

In this paper, we introduce online knapsack problems with a resource buffer. In the problems, we are given a knapsack with capacity 1, a buffer with capacity R >= 1, and items that arrive one by one. Each arriving item has to be taken into the buffer or discarded on its arrival irrevocably. When every item has arrived, we transfer a subset of items in the current buffer into the knapsack. Our goal is to maximize the total value of the items in the knapsack. We consider four variants depending on whether items in the buffer are removable (i.e., we can remove items in the buffer) or non-removable, and proportional (i.e., the value of each item is proportional to its size) or general. For the general&non-removable case, we observe that no constant competitive algorithm exists for any R >= 1. For the proportional&non-removable case, we show that a simple greedy algorithm is optimal for every R >= 1. For the general&removable and the proportional&removable cases, we present optimal algorithms for small R and give asymptotically nearly optimal algorithms for general R.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Discrete optimization
Keywords
  • Online knapsack problem
  • Resource augmentation
  • Competitive analysis

Metrics

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

References

  1. Susanne Albers, Arindam Khan, and Leon Ladewig. Improved Online Algorithms for Knapsack and GAP in the Random Order Model. In Proceedings of APPROX/RANDOM, pages 22:1-22:23, 2019. Google Scholar
  2. Badanidiyuru Ashwinkumar and Robert Kleinberg. Randomized Online Algorithms for the Buyback Problem. In Internet and Network Economics, pages 529-536, 2009. Google Scholar
  3. Moshe Babaioff, Jason D. Hartline, and Robert D. Kleinberg. Selling Ad Campaigns: Online Algorithms with Cancellations. In Proceedings of EC, 2009. Google Scholar
  4. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Proceedings of APPROX/RANDOM, pages 16-28. Springer, 2007. Google Scholar
  5. Marek Cygan, Łukasz Jeż, and Jiří Sgall. Online Knapsack Revisited. Theory of Computing Systems, 58(1):153-190, 2016. Google Scholar
  6. Xin Han, Yasushi Kawase, and Kazuhisa Makino. Online Unweighted Knapsack Problem with Removal Cost. Algorithmica, 70(1):76-91, 2014. Google Scholar
  7. Xin Han, Yasushi Kawase, and Kazuhisa Makino. Randomized algorithms for online knapsack problems. Theoretical Computer Science, 562:395-405, 2015. Google Scholar
  8. Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku. Online Knapsack Problems with a Resource Buffer. CoRR, abs/1909.10016, 2019. URL: http://arxiv.org/abs/1909.10016.
  9. Kazuo Iwama and Shiro Taketomi. Removable Online Knapsack Problems. In Proceeding of ICALP, pages 293-305, 2002. Google Scholar
  10. Kazuo Iwama and Guochuan Zhang. Optimal Resource Augmentations for Online Knapsack. In Proceedings of APPROX/RANDOM, pages 180-188, 2007. Google Scholar
  11. Yasushi Kawase, Xin Han, and Kazuhisa Makino. Proportional cost buyback problem with weight bounds. Theoretical Computer Science, 2016. Google Scholar
  12. Yasushi Kawase, Xin Han, and Kazuhisa Makino. Unit Cost Buyback Problem. Theory of Computing Systems, 2018. Google Scholar
  13. Yasushi Kawase and Atsushi Iwasaki. Near-Feasible Stable Matchings with Budget Constraints. In Proceedings of IJCAI, pages 242-248, 2017. Google Scholar
  14. Yasushi Kawase and Atsushi Iwasaki. Approximately Stable Matchings with Budget Constraints. In Proceedings of AAAI, pages 242-248, 2018. Google Scholar
  15. Yasushi Kawase and Atsushi Iwasaki. Approximately Stable Matchings with General Constraints. CoRR, abs/1907.04163, 2019. URL: http://arxiv.org/abs/1907.04163.
  16. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer-Verlag Berlin Heidelberg, 2004. Google Scholar
  17. Anton J. Kleywegt and Jason D. Papastavrou. The dynamic and stochastic knapsack problem. Operations research, 46(1):17-35, 1998. Google Scholar
  18. Dennis Komm. An Introduction to Online Computation. Springer, 2016. Google Scholar
  19. Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68(1):73-104, 1995. Google Scholar
  20. Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. In Proceedings of WWW, pages 1243-1244, 2008. 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