Document Open Access Logo

Online Unit Profit Knapsack with Untrusted Predictions

Authors Joan Boyar , Lene M. Favrholdt , Kim S. Larsen

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.20.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Joan Boyar
  • University of Southern Denmark, Odense, Denmark
Lene M. Favrholdt
  • University of Southern Denmark, Odense, Denmark
Kim S. Larsen
  • University of Southern Denmark, Odense, Denmark

Funding

Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B.

Cite AsGet BibTex

Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. Online Unit Profit Knapsack with Untrusted Predictions. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.20

Abstract

A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, previous work on online algorithms with untrusted predictions generally studied problems where an online algorithm with a constant competitive ratio is known. The prediction, possibly obtained from a machine learning source, that our algorithm uses is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a/â where a is the actual value for this average size and â is the prediction. The algorithm presented achieves a competitive ratio of 1/(2r) for r ≥ 1 and r/2 for r ≤ 1. Using an adversary technique, we show that this is optimal in some sense, giving a trade-off in the competitive ratio attainable for different values of r. Note that the result for accurate advice, r = 1, is only 1/2, but we show that no deterministic algorithm knowing the value a can achieve a competitive ratio better than (e-1)/e ≈ 0.6321 and present an algorithm with a matching upper bound. We also show that this latter algorithm attains a competitive ratio of r (e-1)/e for r ≤ 1 and (e-r)/e for 1 ≤ r < e, and no deterministic algorithm can be better for both r < 1 and 1 < r < e.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online algorithms
  • untrusted predictions
  • knapsack problem
  • competitive analysis

Metrics

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

Related Versions

References

  1. Sara Ahmadian, Hossein Esfandiari, Vahab Mirrokni, and Binghui Peng. Robust load balancing with machine learned advice. In 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 20-34. SIAM, 2022. Google Scholar
  2. Spyros Angelopoulos. Online search with a hint. In 12th Innovations in Theoretical Computer Science Conference (ITCS), volume 185 of LIPIcs, pages 51:1-51:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  3. Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. In 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151 of LIPIcs, pages 52:1-52:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  4. Spyros Angelopoulos and Shahin Kamali. Contract scheduling with predictions. In 35th AAAI Conference on Artificial Intelligence (AAAI), 33rd Conference on Innovative Applications of Artificial Intelligence (IAAI), 11th Symposium on Educational Advances in Artificial Intelligence (EAAI), pages 11726-11733. AAAI Press, 2021. Google Scholar
  5. Spyros Angelopoulos, Shahin Kamali, and Kimia Shadkami. Online bin packing with predictions. ArXiv, 2021. URL: http://arxiv.org/abs/2102.03311.
  6. Spyros Angelopoulos, Shahin Kamali, and Dehou Zhang. Online search with best-price and query-based predictions. ArXiv, 2021. URL: http://arxiv.org/abs/2112.01592.
  7. Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 345-355. PMLR, 2020. Google Scholar
  8. Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7933-7944. Curran Associates, Inc., 2020. Google Scholar
  9. Etienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In 33rd Annual conference on Neural Information Processing Systems (NeurIPS), pages 15350-15359. Curran Associates, Inc., 2020. Google Scholar
  10. Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In 33rd Annual conference on Neural Information Processing Systems (NeurIPS), pages 20083-20094. Curran Associates, Inc., 2020. Google Scholar
  11. Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-19. SIAM, 2022. Google Scholar
  12. Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning-augmented weighted paging. In 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67-89. SIAM, 2022. Google Scholar
  13. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 822-831. PMLR, 2020. Google Scholar
  14. Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, and Peter Rossmanith. The online knapsack problem: Advice and randomization. Theoretical Computer Science, 527:61-72, 2014. Google Scholar
  15. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online Algorithms with Advice: A Survey. ACM Computing Surveys, 50(2):1-34, 2017. Article No. 19. Google Scholar
  16. Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. Online unit profit knapsack with untrusted predictions. ArXiv, 2022. URL: http://arxiv.org/abs/2203.00285.
  17. 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:463-472, 2001. Google Scholar
  18. Marek Cygan, Łukasz Jeż, and Jirí Sgall. Online knapsack revisited. Theory of Computing Systems, 58, 2016. Google Scholar
  19. Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 2319-2327. PMLR, 2019. Google Scholar
  20. Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. In 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 285-294. ACM, 2021. Google Scholar
  21. Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. In Pre-Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), 2021. Google Scholar
  22. Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrović, and Ronitt Rubinfeld. Online page migration with ML advice. ArXiv, 2020. URL: http://arxiv.org/abs/2006.05028.
  23. Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 69:1-69:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  24. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004. Google Scholar
  25. Rohan Kodialam. Optimal algorithms for ski rental with soft machine-learned predictions. ArXiv, 2019. URL: http://arxiv.org/abs/1903.00092.
  26. Arvind Kumar and Bashir Alam. Task scheduling in real time systems with energy harvesting and energy minimization. Journal of Computational Science, 14(8):1126-1133, 2018. Google Scholar
  27. Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1859-1877. SIAM, 2020. Google Scholar
  28. Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing. In 29th Annual European Symposium on Algorithms (ESA), volume 204 of LIPIcs, pages 59:1-59:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  29. Russell Lee, Mohammad H. Hajiesmaili, and Jian Li. Learning-assisted competitive algorithms for peak-aware energy scheduling. ArXiv, 2020. URL: http://arxiv.org/abs/1911.07972.
  30. Russell Lee, Jessica Maghakian, Mohammad H. Hajiesmaili, Jian Li, Ramesh K. Sitaraman, and Zhenhua Liu. Online peak-aware energy scheduling with untrusted advice. In 12th ACM International Conference on Future Energy Systems (e-Energy), pages 107-123. ACM, 2021. Google Scholar
  31. Shi Li and Jiayi Xian. Online unrelated machine load balancing with predictions revisited. In 38th International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 6523-6532. PMLR, 2021. Google Scholar
  32. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In 35th International Conference on Machine Learning (ICML), volume 80, pages 3302-3311. PMLR, 2018. Google Scholar
  33. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4):24:1-24:25, 2021. Google Scholar
  34. Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68:73-104, 1995. Google Scholar
  35. Andres Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. In 30th Annual Conference on Neural Information Processing Systems (NIPS), pages 1858-1866. Curran Associates, Inc., 2017. Google Scholar
  36. Michael Mitzenmacher. Scheduling with Predictions and the Price of Misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151 of LIPIcs, pages 14:1-14:18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020. Google Scholar
  37. Michael Mitzenmacher. Queues with small advice. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), pages 1-12, 2021. Google Scholar
  38. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. ArXiv, 2020. URL: http://arxiv.org/abs/2006.09123.
  39. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In 31st Annual Conference on Neural Information Processing Systems (NeurIPS), pages 9661-9670. Curran Associates, Inc., 2018. Google Scholar
  40. Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1834-1845. SIAM, 2020. Google Scholar
  41. Daan Rutten and Debankur Mukherjee. A new approach to capacity scaling augmented with unreliable machine learning predictions. ArXiv, 2021. URL: http://arxiv.org/abs/2101.12160.
  42. Shufan Wang and Jian Li. Online algorithms for multi-shop ski rental with machine learned predictions. In 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2035-2037. International Foundation for Autonomous Agents and Multiagent Systems, 2020. Google Scholar
  43. Alexander Wei. Better and simpler learning-augmented online caching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 176 of LIPIcs, pages 60:1-60:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  44. Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. ArXiv, 2020. URL: http://arxiv.org/abs/2010.11443.
  45. Ali Zeynali, Bo Sun Mohammad Hajiesmaili, and Adam Wierman. Data-driven competitive algorithms for online knapsack and set cover. In 35th AAAI Conference on Artificial Intelligence (AAAI), 2021. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact