License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.52
URN: urn:nbn:de:0030-drops-117372
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11737/
Go to the corresponding LIPIcs Volume Portal


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

Online Computation with Untrusted Advice

pdf-format:
LIPIcs-ITCS-2020-52.pdf (0.5 MB)


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.

BibTeX - Entry

@InProceedings{angelopoulos_et_al:LIPIcs:2020:11737,
  author =	{Spyros Angelopoulos and Christoph D{\"u}rr and Shendan Jin and Shahin Kamali and Marc Renault},
  title =	{{Online Computation with Untrusted Advice}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11737},
  URN =		{urn:nbn:de:0030-drops-117372},
  doi =		{10.4230/LIPIcs.ITCS.2020.52},
  annote =	{Keywords: Online computation, competitive analysis, advice complexity, robust algorithms, untrusted advice}
}

Keywords: Online computation, competitive analysis, advice complexity, robust algorithms, untrusted advice
Seminar: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 10.01.2020


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