Document Open Access Logo

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

Author Jesper W. Mikkelsen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.39.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Jesper W. Mikkelsen

Cite As Get BibTex

Jesper W. Mikkelsen. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.39

Abstract

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].

Subject Classification

Keywords
  • online algorithms
  • advice complexity
  • information theory
  • randomization

Metrics

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

References

  1. Anna Adamaszek, Artur Czumaj, Matthias Englert, and Harald Räcke. Almost tight bounds for reordering buffer management. In STOC, 2011. Google Scholar
  2. Anna Adamaszek, Marc P. Renault, Adi Rosén, and Rob van Stee. Reordering buffer management with advice. In WAOA, 2013. Google Scholar
  3. Susanne Albers and Matthias Hellwig. Online makespan minimization with parallel schedules. In SWAT, 2014. Google Scholar
  4. Christoph Ambühl. On the list update problem. PhD thesis, ETH Zürich, 2002. Google Scholar
  5. Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc P. Renault, and Adi Rosén. Online bin packing with advice of small size. In WADS, 2015. Google Scholar
  6. Yossi Azar, Andrei Z. Broder, and Mark S. Manasse. On-line choice of on-line algorithms. In SODA, 1993. Google Scholar
  7. Yossi Azar, Iftah Gamzu, and Ran Roth. Submodular max-sat. In ESA, 2011. Google Scholar
  8. Amotz Bar-Noy, Rajeev Motwani, and Joseph (Seffi) Naor. The greedy algorithm is optimal for on-line edge coloring. Inf. Process. Lett., 44(5):251-253, 1992. Google Scholar
  9. Dwight R. Bean. Effective coloration. J. Symb. Log., 41(2):469-480, 1976. Google Scholar
  10. Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, and Lucia Keller. Online coloring of bipartite graphs with and without advice. Algorithmica, 70(1):92-111, 2014. Google Scholar
  11. Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, Sacha Krug, and Björn Steffen. On the advice complexity of the online L(2, 1)-coloring problem on paths and cycles. Theor. Comput. Sci., 554:22-39, 2014. Google Scholar
  12. Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. Machine Learning, 39(1):35-58, 2000. Google Scholar
  13. Hans-Joachim Böckenhauer, Richard Dobson, Sacha Krug, and Kathleen Steinhöfel. On energy-efficient computations with advice. In COCOON, 2015. Google Scholar
  14. Hans-Joachim Böckenhauer, Sascha Geulen, Dennis Komm, and Walter Unger. Constructing randomized online algorithms from algorithms with advice. ETH-Zürich, 2015. Google Scholar
  15. Hans-Joachim Böckenhauer, Juraj Hromkovič, Dennis Komm, Sacha Krug, Jasmin Smula, and Andreas Sprock. The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci., 554:95-108, 2014. Google Scholar
  16. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, and Richard Královič. On the advice complexity of the k-server problem. In ICALP (1), 2011. Google Scholar
  17. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. On the advice complexity of online problems. In ISAAC, 2009. Google Scholar
  18. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Google Scholar
  19. 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
  20. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. Advice complexity for a class of online problems. In STACS, 2015. Google Scholar
  21. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. Weighted online problems with advice. In submission, 2016. Google Scholar
  22. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. On the list update problem with advice. In LATA, 2014. Google Scholar
  23. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. Online bin packing with advice. In STACS, 2014. Full paper to appear in Algorithmica. Google Scholar
  24. Carl Burch. Machine learning in metrical task systems and other on-line problems. PhD thesis, Carnegie Mellon University, 2000. http://cburch.com/pub/thesis.ps.gz. Google Scholar
  25. Marek Chrobak, Lawrence L. Larmore, Carsten Lund, and Nick Reingold. A better lower bound on the competitive ratio of the randomized 2-server problem. Inf. Process. Lett., 63(2):79-83, 1997. Google Scholar
  26. Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley, 2006. Google Scholar
  27. Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu. Dynamic optimality - almost. SIAM J. Comput., 37(1):240-251, 2007. Google Scholar
  28. Stefan Dobrev, Rastislav Královič, and Dana Pardubská. Measuring the problem-relevant information in input. RAIRO - Theor. Inf. Appl., 43(3):585-613, 2009. Google Scholar
  29. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theor. Comput. Sci., 412(24):2642-2656, 2011. Google Scholar
  30. Leah Epstein and Rob van Stee. On the online unit clustering problem. ACM Transactions on Algorithms, 7(1):1-18, 2010. Google Scholar
  31. Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, and Sundar Vishwanathan. Competitive algorithms for layered graph traversal. SIAM J. Comput., 28(2):447-462, 1998. Google Scholar
  32. Michal Forišek, Lucia Keller, and Monika Steinová. Advice complexity of online graph coloring. Unpublished manuscript, 2012. Google Scholar
  33. Magnús M. Halldórsson and Mario Szegedy. Lower bounds for on-line graph coloring. Theor. Comput. Sci., 130(1):163-174, 1994. Google Scholar
  34. Juraj Hromkovič, Rastislav Královič, and Richard Královič. Information complexity of online problems. In MFCS, 2010. Google Scholar
  35. Bala Kalyanasundaram and Kirk Pruhs. Online weighted matching. J. Algorithms, 14(3):478-488, 1993. Google Scholar
  36. Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan S. Owicki. Competitive randomized algorithms for non-uniform problems. In SODA, 1990. Google Scholar
  37. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In STOC, 1990. Google Scholar
  38. Dennis Komm, Rastislav Královic, Richard Královic, and Christian Kudahl. Advice complexity of the online induced subgraph problem. CoRR, abs/1512.05996, 2015. Google Scholar
  39. Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105-118, 2009. Google Scholar
  40. Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput., 108(2):212-261, 1994. Google Scholar
  41. Jesper W. Mikkelsen. Optimal online edge coloring of planar graphs with advice. In CIAC, 2015. Google Scholar
  42. Jesper W. Mikkelsen. Randomization can be as helpful as a glimpse of the future in online computation. CoRR, abs/1511.05886, November 2015. Google Scholar
  43. Shuichi Miyazaki. On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett., 114(12):714-717, 2014. Google Scholar
  44. Tobias Mömke. A competitive ratio approximation scheme for the k-server problem in fixed finite metrics. CoRR, abs/1303.2963, 2013. Google Scholar
  45. Marc P. Renault and Adi Rosén. On online algorithms with advice for the k-server problem. Theory Comput. Syst., 56(1):3-21, 2015. Google Scholar
  46. Jasmin Smula. Information Content of Online Problems, Advice versus Determinism and Randomization. PhD thesis, ETH Zürich, 2015. Google Scholar
  47. Boris Teia. A lower bound for randomized list update algorithms. Inf. Process. Lett., 47(1):5-9, 1993. Google Scholar
  48. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In FOCS, 1977. 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 About DROPS Imprint Privacy Contact