A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey

  • Chapter
  • First Online:
Computing with New Resources

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8808))

Abstract

We survey how the advice complexity of online algorithms can be used to obtain lower bounds on the performance of randomized online algorithms. Online algorithms with advice may query an oracle that knows the whole input from the start to solve some instance of an online problem. This is done by reading a finite prefix of some infinite binary advice tape, which is created by the oracle before the first piece of input is processed. Similarly, a randomized online algorithm may use a binary tape where every bit is chosen uniformly at random.

In this survey, we review a technique, similar to Yao’s principle, which allows statements on the advice complexity of some given online problem to translate to results on the power of randomization for this problem in terms of lower bounds. We give some examples where this technique works and how it is applied, and show its limitations and that it is tight in a very general sense.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Barhum, K.: Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 77–88. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

  2. Barhum, K., Böckenhauer, H.-J., Forišek, M., Gebauer, H., Hromkovič, J., Krug, S., Smula, J., Steffen, B.: On the Power of Advice and Randomization for the Disjoint Path Allocation Problem. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 89–101. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

  3. Bianchi, M.P., Böckenhauer, H.-J., Hromkovič, J., Keller, L.: Online Coloring of Bipartite Graphs with and without Advice. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 519–530. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  4. Bianchi, M.P., Böckenhauer, H.-J., Hromkovič, J., Krug, S., Steffen, B.: On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 53–64. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  5. Bansal, N., Buchbinder, N., Madry, A., Naor, J.: A polylogarithmic-competitive algorithm for the \(k\)-server problem (extended abstract). In: Proc. of FOCS 2011, pp. 267–276 (2011)

    Google Scholar 

  6. Böckenhauer, H.-J., Hromkovič, J., Komm, D., Královič, R., Rossmanith, P.: On the Power of Randomness versus Advice in Online Computation. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Languages Alive. LNCS, vol. 7300, pp. 30–43. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  7. Böckenhauer, H.-J., Hromkovič, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 493–505. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  8. Böckenhauer, H.J., Komm, D., Královič, R., Královič, R.: On the advice complexity of the \(k\)-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.): ICALP 2011, Part I. LNCS, vol. 6755, pp. 207–218. Springer, Heidelberg (2011)

    Google Scholar 

  9. Böckenhauer, H.-J., Komm, D., Královič, R., Královič, R., Mömke, T.: On the Advice Complexity of Online Problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 331–340. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  10. Böckenhauer, H.-J., Komm, D., Královič, R., Rossmanith, P.: On the Advice Complexity of the Knapsack Problem. In: Fernández-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 61–72. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  11. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)

    Google Scholar 

  12. Boyar, J., Kamali, S., Larsen, K.S., López-Ortiz, A.: Online bin packing with advice. In: Proc. of STACS 2014. LIPIcs 25, pp. 174–186. Schloss Dagstuhl (2014)

    Google Scholar 

  13. Boyar, J., Kamali, S., Larsen, K.S., López-Ortiz, A.: On the List Update Problem with Advice. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 210–221. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

  14. Dorrigiv, R., He, M., Zeh, N.: On the Advice Complexity of Buffer Management. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 136–145. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  15. Dobrev, S., Královič, R., Královič, R.: Independent Set with Advice: The Impact of Graph Knowledge. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 2–15. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  16. I. Seleceniova. Personal communication.

    Google Scholar 

  17. Dobrev, S., Královič, R., Markou, E.: Online Graph Exploration with Advice. In: Even, G., Halldórsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 267–278. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  18. Dobrev, S., Královič, R., Pardubská, D.: How Much Information about the Future Is Needed? In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 247–258. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  19. Dohrau, J.: Online makespan scheduling with sublinear advice. Technical Report, ETH Zurich (2013)

    Google Scholar 

  20. Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online Computation with Advice. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 427–438. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  21. Elias, P.: Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory 21(2), 194–203 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  22. Forišek, M., Keller, L., Steinová, M.: Advice Complexity of Online Coloring for Paths. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 228–239. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  23. Gupta, S., Kamali, S., López-Ortiz, A.: On Advice Complexity of the k-server Problem under Sparse Metrics. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 55–67. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  24. Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics, 2nd ed. Addison-Wesley (1994)

    Google Scholar 

  25. Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance \(2\). SIAM Journal on Discrete Mathemtics 5(4), 586–595 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  26. Hromkovič, J., Královič, R., Královič, R.: Information Complexity of Online Problems. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 24–36. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  27. Hromkovič, J., Mömke, T., Steinhöfel, K., Widmayer, P.: Job shop scheduling with unit length tasks: Bounds and algorithms. Algorithmic Operations Research 2(1), 1–14 (2007)

    MathSciNet  MATH  Google Scholar 

  28. Komm, D., Královič, R.: Advice complexity and barely random algorithms. Theoretical Informatics and Applications (RAIRO) 45(2), 249–267 (2011)

    Google Scholar 

  29. Komm, D., Královič, R., Mömke, T.: On the Advice Complexity of the Set Cover Problem. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 241–252. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  30. Koutsoupias, E., Papadimitriou, C.H.: On the \(k\)-server conjecture. Journal of the ACM 42(5), 971–983 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  31. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. In: Proc. of STOC 1998, pp. 322–333 (1988)

    Google Scholar 

  32. Renault, M.P., Rosén, A.: On Online Algorithms with Advice for the k-Server Problem. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol. 7164, pp. 198–210. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  33. Renault, M.P., Rosén, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. CoRR abs/1311.7589 (2013)

    Google Scholar 

  34. Seibert, S., Sprock, A., Unger, W.: Advice Complexity of the Online Coloring Problem. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 345–357. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  35. Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: Proc. of FOCS 1977, pp. 222–227. IEEE Computer Society (1977)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, ETH Zürich, Universtitätsstrasse 6, 8092, Zürich, Switzerland

    Hans-Joachim Böckenhauer, Juraj Hromkovič & Dennis Komm

Authors
  1. Hans-Joachim Böckenhauer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juraj Hromkovič
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dennis Komm
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juraj Hromkovič .

Editor information

Editors and Affiliations

  1. Department of Computer Science, The University of Auckland, Auckland, New Zealand

    Cristian S. Calude

  2. University of Latvia, Riga, Latvia

    Rūsiņš Freivalds

  3. School of Informatics, Kyoto University, Kyoto, Japan

    Iwama Kazuo

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Böckenhauer, HJ., Hromkovič, J., Komm, D. (2014). A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey. In: Calude, C., Freivalds, R., Kazuo, I. (eds) Computing with New Resources. Lecture Notes in Computer Science(), vol 8808. Springer, Cham. https://doi.org/10.1007/978-3-319-13350-8_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-13350-8_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-13349-2

  • Online ISBN: 978-3-319-13350-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics