Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation

Jesper With Mikkelsen

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

26 Downloads (Pure)

Abstrakt

We provide simple but surprisingly useful direct product theorems for proving lower bounds on online algorithms with a limited amount of advice about the future. Intuitively, our direct product theorems say that if b bits of advice are needed to ensure a cost of at most t for some problem, then r*b bits of advice are needed to ensure a total cost of at most r*t when solving r independent instances of the problem. Using our direct product theorems, we are able to translate decades of research on randomized online algorithms to the advice complexity model. Doing so improves significantly on the previous best advice complexity lower bounds for many online problems, or provides the first known lower bounds. For example, we show that - A paging algorithm needs Omega(n) bits of advice to achieve a competitive ratio better than H_k = Omega(log k), where k is the cache size. Previously, it was only known that Omega(n) bits of advice were necessary to achieve a constant competitive ratio smaller than 5/4. - Every O(n^{1-epsilon})-competitive vertex coloring algorithm must use Omega(n log n) bits of advice. Previously, it was only known that Omega(n log n) bits of advice were necessary to be optimal. For certain online problems, including the MTS, k-server, metric matching, paging, list update, and dynamic binary search tree problem, we prove that randomization and sublinear advice are equally powerful (if the underlying metric space or node set is finite). This means that several long-standing open questions regarding randomized online algorithms can be equivalently stated as questions regarding online algorithms with sublinear advice. For example, we show that there exists a deterministic O(log k)-competitive k-server algorithm with sublinear advice if and only if there exists a randomized O(log k)-competitive k-server algorithm without advice. Technically, our main direct product theorem is obtained by extending an information theoretical lower bound technique due to Emek, Fraigniaud, Korman, and Rosén [ICALP'09].
OriginalsprogEngelsk
Titel43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
RedaktørerIoannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi
ForlagSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Publikationsdato2016
Sider39:1-39:14
ISBN (Elektronisk)978-3-95977-013-2
DOI
StatusUdgivet - 2016
Begivenhed43rd International Colloquium on Automata, Languages, and Programming - Rome, Italien
Varighed: 12. jul. 201615. jul. 2016
Konferencens nummer: 43

Konference

Konference43rd International Colloquium on Automata, Languages, and Programming
Nummer43
LandItalien
ByRome
Periode12/07/201615/07/2016
NavnLeibniz International Proceedings in Informatics
Vol/bind55
ISSN1868-8969

    Fingerprint

Citationsformater

Mikkelsen, J. W. (2016). Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation. I I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (red.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (s. 39:1-39:14). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Leibniz International Proceedings in Informatics, Bind. 55 https://doi.org/10.4230/LIPIcs.ICALP.2016.39