Document Open Access Logo

Online Algorithms with Randomly Infused Advice

Authors Yuval Emek , Yuval Gil, Maciej Pacut , Stefan Schmid

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.44.pdf
  • Filesize: 0.77 MB
  • 19 pages

Document Identifiers

Author Details

Yuval Emek
  • Technion, Haifa, Israel
Yuval Gil
  • Technion, Haifa, Israel
Maciej Pacut
  • TU Berlin, Germany
Stefan Schmid
  • TU Berlin, Germany

Funding

  • Emek, Yuval: VATAT Fund to the Technion Artificial Intelligence Hub (Tech.AI).
  • Pacut, Maciej: Austrian Science Fund (FWF) and the German Research Foundation (DFG), grant I 4800-N (ADVISE), 2020-2023.
  • Schmid, Stefan: Austrian Science Fund (FWF) and the German Research Foundation (DFG), grant I 4800-N (ADVISE), 2020-2023.

Cite AsGet BibTex

Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online Algorithms with Randomly Infused Advice. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.44

Abstract

We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In contrast to prior work, our method, referred to as randomly infused advice (RIA), does not make any assumptions about the input sequence and does not rely on the development of designated online algorithms. Rather, it can be applied to existing online randomized algorithms, introducing a means to evaluate their performance in scenarios that lie outside the radical worst-case regime. More concretely, an online algorithm ALG with RIA benefits from pieces of advice generated by an omniscient but not entirely reliable oracle. The crux of the new method is that the advice is provided to ALG by writing it into the buffer ℬ from which ALG normally reads its random bits, hence allowing us to augment it through a very simple and non-intrusive interface. The (un)reliability of the oracle is captured via a parameter 0 ≤ α ≤ 1 that determines the probability (per round) that the advice is successfully infused by the oracle; if the advice is not infused, which occurs with probability 1 - α, then the buffer ℬ contains fresh random bits (as in the classic online setting). The applicability of the new RIA method is demonstrated by applying it to three extensively studied online problems: paging, uniform metrical task systems, and online set cover. For these problems, we establish new upper bounds on the competitive ratio of classic online algorithms that improve as the infusion parameter α increases. These are complemented with (often tight) lower bounds on the competitive ratio of online algorithms with RIA for the three problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • competitive analysis
  • advice

Metrics

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

Related Versions

References

  1. Dimitris Achlioptas, Marek Chrobak, and John Noga. Competitive analysis of randomized paging algorithms. Theor. Comput. Sci., 234(1-2):203-218, 2000. Google Scholar
  2. Susanne Albers, Lene M. Favrholdt, and Oliver Giel. On paging with locality of reference. J. Comput. Syst. Sci., 70(2):145-175, 2005. Google Scholar
  3. Susanne Albers and Dario Frascaria. Quantifying competitiveness in paging with locality of reference. Algorithmica, 80(12):3563-3596, 2018. Google Scholar
  4. Susanne Albers and Maximilian Janke. Scheduling in the random-order model. Algorithmica, 83(9):2803-2832, 2021. Google Scholar
  5. Susanne Albers, Arindam Khan, and Leon Ladewig. Best fit bin packing with random order revisited. Algorithmica, 83(9):2833-2858, 2021. Google Scholar
  6. Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and GAP in the random order model. Algorithmica, 83(6):1750-1785, 2021. Google Scholar
  7. Susanne Albers and Sonja Lauer. On list update with locality of reference. J. Comput. Syst. Sci., 82(5):627-653, 2016. Google Scholar
  8. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Trans. Algorithms, 2(4):640-660, 2006. Google Scholar
  9. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM J. Comput., 39(2):361-370, 2009. Google Scholar
  10. 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 2020 (ITCS), volume 151, pages 52:1-52:15, 2020. Google Scholar
  11. Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 345-355. PMLR, 2020. Google Scholar
  12. Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020. Google Scholar
  13. Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning-augmented weighted paging. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 67-89. SIAM, 2022. Google Scholar
  14. Yair Bartal and Eddie Grove. The harmonic k-server algorithm is competitive. J. ACM, 47(1):1-15, 2000. Google Scholar
  15. Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, and Tjark Vredeveld. Average case and smoothed competitive analysis of the multi-level feedback algorithm. In 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 462-471, 2003. Google Scholar
  16. Laszlo A. Belady. A study of replacement algorithms for virtual-storage computer. IBM Syst. J., 5(2):78-101, 1966. Google Scholar
  17. Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, and Avi Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2-14, 1994. Google Scholar
  18. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke. Online algorithms with advice: The tape model. Inf. Comput., 254:59-83, 2017. Google Scholar
  19. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Google Scholar
  20. Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. Competitive paging with locality of reference. J. Comput. Syst. Sci., 50(2):244-258, 1995. Google Scholar
  21. Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, 1992. Google Scholar
  22. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online algorithms with advice: A survey. ACM Comput. Surv., 50(2), 2017. Google Scholar
  23. Joan Boyar, Sandy Irani, and Kim S. Larsen. A comparison of performance measures for online algorithms. Algorithmica, 72(4):969-994, 2015. Google Scholar
  24. Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci., 3(2-3):93-263, 2009. Google Scholar
  25. Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Math. Oper. Res., 34(2):270-286, 2009. Google Scholar
  26. Marek Chrobak and Lawrence L. Larmore. The server problem and on-line games. In On-Line Algorithms, Proceedings of a DIMACS Workshop, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 11-64. DIMACS/AMS, 1991. Google Scholar
  27. José R. Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, and Alexandros Tsigonias-Dimitriadis. The secretary problem with independent sampling. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2047-2058. SIAM, 2021. Google Scholar
  28. Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav Královic, Richard Královic, Sacha Krug, and Tobias Mömke. Improved analysis of the online set cover problem with advice. Theor. Comput. Sci., 689:96-107, 2017. Google Scholar
  29. Reza Dorrigiv and Alejandro López-Ortiz. A survey of performance measures for on-line algorithms. SIGACT News, 36(3):67-81, 2005. Google Scholar
  30. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theor. Comput. Sci., 412(24):2642-2656, 2011. Google Scholar
  31. Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online algorithms with randomly infused advice. CoRR, abs/2302.05366, 2023. URL: https://doi.org/10.48550/arXiv.2302.05366.
  32. Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms. J. Algorithms, 12(4):685-699, 1991. Google Scholar
  33. Amos Fiat and Manor Mendel. Better algorithms for unfair metrical task systems and applications. SIAM J. Comput., 32(6):1403-1422, 2003. Google Scholar
  34. Greg N. Frederickson. Probabilistic analysis for simple one- and two-dimensional bin packing algorithms. Inf. Process. Lett., 11:156-161, 1980. Google Scholar
  35. Edward F. Grove. Online bin packing with lookahead. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 430-436. ACM/SIAM, 1995. Google Scholar
  36. Sandy Irani and Steven S. Seiden. Randomized algorithms for metrical task systems. Theor. Comput. Sci., 194(1-2):163-182, 1998. Google Scholar
  37. Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, volume 168 of LIPIcs, pages 69:1-69:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  38. Anna R. Karlin and Elias Koutsoupias. Beyond competitive analysis. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 529-546. Cambridge University Press, 2020. URL: https://doi.org/10.1017/9781108637435.031.
  39. Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke. Randomized online algorithms with high probability guarantees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25, pages 470-481, 2014. Google Scholar
  40. Simon Korman. On the use of randomization in the online set cover problem. Master’s thesis, Weizmann Institute of Science, Rehovot, Israel, 2004. Google Scholar
  41. Elias Koutsoupias and Christos H. Papadimitriou. Beyond competitive analysis. SIAM J. Comput., 30(1):300-317, 2000. Google Scholar
  42. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4):24:1-24:25, 2021. Google Scholar
  43. Lyle A. McGeoch and Daniel Dominic Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6:816-825, 1991. Google Scholar
  44. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google Scholar
  45. Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. In Mikhail J. Atallah, editor, Algorithms and Theory of Computation Handbook, Chapman & Hall/CRC Applied Algorithms and Data Structures series. CRC Press, 1999. Google Scholar
  46. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages 9684-9693, 2018. Google Scholar
  47. Jan Reineke and Alejandro Salinger. On the smoothness of paging algorithms. Theory Comput. Syst., 62(2):366-418, 2018. Google Scholar
  48. Ronald L. Rivest. On self-organizing sequential search heuristics. Commun. ACM, 19(2):63-67, 1976. Google Scholar
  49. Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1834-1845. SIAM, 2020. Google Scholar
  50. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. URL: https://doi.org/10.1145/2786.2793.
  51. Jeffery R. Westbrook. Randomized algorithms for multiprocessor page migration. SIAM J. Comput., 23(5):951-965, 1994. Google Scholar
  52. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science, Providence, pages 222-227. IEEE Computer Society, 1977. Google Scholar
  53. Neal E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525-541, 1994. URL: https://doi.org/10.1007/BF01189992.
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