License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.13
URN: urn:nbn:de:0030-drops-185474
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18547/
Go to the corresponding LIPIcs Volume Portal

Angelopoulos, Spyros ; Kamali, Shahin

Rényi-Ulam Games and Online Computation with Imperfect Advice

pdf-format:
LIPIcs-MFCS-2023-13.pdf (0.8 MB)

Abstract

We study the nascent setting of online computation with imperfect advice, in which the online algorithm is enhanced by some prediction encoded in the form of an imperfect, and possibly erroneous binary string. The algorithm is oblivious to the advice error, but defines a desired tolerance, namely an upper bound on the number of erroneous advice bits it can tolerate. This is a model that generalizes the Pareto-based advice model, in which the performance of the algorithm is only evaluated at the extreme values of error (namely, if the advice has either no errors, or if it is generated adversarially). It also subsumes the model in which the algorithm elicits a prediction on the online sequence, via imperfect responses to a number of binary queries.
In this work, we establish connections between games with a lying responder, also known as Rényi-Ulam games, and the design and analysis of online algorithms with imperfect advice. Specifically, we demonstrate how to obtain upper and lower bounds on the competitive ratio for important online problems such as time-series search, online bidding, and fractional knapsack. Our techniques provide the first lower bounds for online problems in this model. We also highlight and exploit connections between competitive analysis with imperfect advice and fault-tolerance in multiprocessor systems. Last, we show how to waive the dependence on the tolerance parameter, by means of resource augmentation and robustification.

BibTeX - Entry

@InProceedings{angelopoulos_et_al:LIPIcs.MFCS.2023.13,
  author =	{Angelopoulos, Spyros and Kamali, Shahin},
  title =	{{R\'{e}nyi-Ulam Games and Online Computation with Imperfect Advice}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18547},
  URN =		{urn:nbn:de:0030-drops-185474},
  doi =		{10.4230/LIPIcs.MFCS.2023.13},
  annote =	{Keywords: Online computation, R\'{e}nyi-Ulam games, query models, beyond worst-case analysis}
}

Keywords: Online computation, Rényi-Ulam games, query models, beyond worst-case analysis
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI