Document Open Access Logo

Online Computation with Untrusted Advice

Authors Spyros Angelopoulos , Christoph Dürr , Shendan Jin , Shahin Kamali , Marc Renault

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.52.pdf
  • Filesize: 461 kB
  • 15 pages

Document Identifiers

Author Details

Spyros Angelopoulos
  • Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, Paris, France
Christoph Dürr
  • Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, Paris, France
Shendan Jin
  • Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, Paris, France
Shahin Kamali
  • Department of Computer Science, University of Manitoba, Winnipeg, Canada
Marc Renault
  • Computer Sciences Department, University of Wisconsin - Madison, Madison, WI, USA

Funding

Research supported by the CNRS-PEPS Project Advice.

Cite AsGet BibTex

Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.52

Abstract

The advice model of online computation captures the setting in which the online algorithm is given some partial information concerning the request sequence. This paradigm allows to establish tradeoffs between the amount of this additional information and the performance of the online algorithm. However, unlike real life in which advice is a recommendation that we can choose to follow or to ignore based on trustworthiness, in the current advice model, the online algorithm treats it as infallible. This means that if the advice is corrupt or, worse, if it comes from a malicious source, the algorithm may perform poorly. In this work, we study online computation in a setting in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust and perform well even when the advice is generated in a malicious, adversarial manner. To this end, we focus on well- studied online problems such as ski rental, online bidding, bin packing, and list update. For ski-rental and online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the competitive ratios achieved; this improves upon the framework of Purohit et al. [NeurIPS 2018] in which Pareto-optimality is not necessarily guaranteed. For bin packing and list update, we give online algorithms with worst-case tradeoffs in their competitiveness, depending on whether the advice is trusted or not; this is motivated by work of Lykouris and Vassilvitskii [ICML 2018] on the paging problem, but in which the competitiveness depends on the reliability of the advice. Furthermore, we demonstrate how to prove lower bounds, within this model, on the tradeoff between the number of advice bits and the competitiveness of any online algorithm. Last, we study the effect of randomization: here we show that for ski-rental there is a randomized algorithm that Pareto-dominates any deterministic algorithm with advice of any size. We also show that a single random bit is not always inferior to a single advice bit, as it happens in the standard model.

Subject Classification

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

Metrics

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

Related Versions

References

  1. Susanne Albers. Improved Randomized On-Line Algorithms for the List Update Problem. SIAM J. Comput., 27:682-693, 1998. Google Scholar
  2. Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online Computation with Untrusted Advice. CoRR, abs/1905.05655, 2019. URL: http://arxiv.org/abs/1905.05655.
  3. Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc P. Renault, and Adi Rosén. Online Bin Packing with Advice of Small Size. Theory Comput. Syst., 62(8):2006-2034, 2018. Google Scholar
  4. János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A New and Improved Algorithm for Online Bin Packing. In 26th Annual European Symposium on Algorithms (ESA 2018), pages 5:1-5:14, 2018. Google Scholar
  5. János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A new lower bound for classic online bin packing. CoRR, abs/1807.05554, 2018. URL: http://arxiv.org/abs/1807.05554.
  6. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. On the Advice Complexity of Online Problems. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pages 331-340, 2009. Google Scholar
  7. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online Algorithms with Advice: A Survey. SIGACT News, 47(3):93-129, 2016. Google Scholar
  8. Joan Boyar, Lene M Favrholdt, Christian Kudahl, and Jesper W Mikkelsen. Advice complexity for a class of online problems. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  9. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. On the List Update Problem with Advice. Information and Computation, 253:411-423, 2016. Google Scholar
  10. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. Online Bin Packing with Advice. Algorithmica, 74(1):507-527, 2016. Google Scholar
  11. Marek Chrobak and Claire Kenyon. Competitiveness via Doubling. SIGACT News, pages 115-126, 2006. Google Scholar
  12. Stefan Dobrev, Rastislav Královič, and Dana Pardubská. Measuring the problem-relevant information in input. RAIRO Inform. Theor. Appl., 43(3):585-613, 2009. Google Scholar
  13. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theoret. Comput. Sci., 412(24):2642-2656, 2011. Google Scholar
  14. Sandy Irani. Two results on the list update problem. Inform. Process. Lett., 38:301-306, 1991. Google Scholar
  15. David S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973. Google Scholar
  16. Mikkelsen J.W. Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 39:1-39:14, 2016. Google Scholar
  17. Shahin Kamali and Alejandro López-Ortiz. Better Compression through Better List Update Algorithms. In Data Compression Conference, pages 372-381, 2014. Google Scholar
  18. Anna Karlin, Mark Manasse, Larry Rudolph, and Daniel Sleator. Competitive snoopy caching. Algorithmica, 3:79-119, 1988. Google Scholar
  19. Anna R Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP Acknowledgment and Other Stories about e/(e- 1). Algorithmica, 36:209-224, 2003. Google Scholar
  20. Alejandro López-Ortiz, Spryos Angelopoulos, and Angèle M. Hamel. Optimal Scheduling of Contract Algorithms for Anytime Problems. Journal of Artificial Intelligence Research, 51:533-554, 2014. Google Scholar
  21. Thodoris Lykouris and Sergei Vassilvitskii. Competitive Caching with Machine Learned Advice. In Proceedings of the 35th International Conference on Machine Learning, ICML, pages 3302-3311, 2018. Google Scholar
  22. Adam Meyerson. The Parking Permit Problem. In 46th Annual IEEE Symposium on Foundations of Computer Science, pages 274-284. IEEE, 2005. Google Scholar
  23. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving Online Algorithms via ML Predictions. In Advances in Neural Information Processing Systems, volume 31, pages 9661-9670, 2018. Google Scholar
  24. Marc P. Renault, Adi Rosén, and Rob van Stee. Online algorithms with advice for bin packing and scheduling problems. Theor. Comput. Sci., 600:155-170, 2015. URL: https://doi.org/10.1016/j.tcs.2015.07.050.
  25. Stuart J. Russell and Shlomo Zilberstein. Composing real-time systems. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pages 212-217, 1991. Google Scholar
  26. Daniel Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28:202-208, 1985. Google Scholar
  27. Daniel D. Sleator and Robert Endre Tarjan. Self-adjusting Binary Search Trees. Jour. of the ACM, 32:652-686, 1985. 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