{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T08:52:43Z","timestamp":1769071963968,"version":"3.49.0"},"reference-count":105,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,8,31]],"date-time":"2016-08-31T00:00:00Z","timestamp":1472601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2016,8,31]]},"abstract":"<jats:p>Online algorithms with advice is an area of research where one attempts to measure how much knowledge of the future is necessary to achieve a given competitive ratio. The lower bound results give robust bounds on what is possible using semi-online algorithms. On the other hand, when the advice is of an obtainable form, algorithms using advice can lead to semi-online algorithms. There are strong relationships between advice complexity and randomization, and advice complexity has led to the introduction of the first complexity classes for online problems.<\/jats:p>\n          <jats:p>This survey concerning online algorithms with advice explains the models, motivates the study in general, presents some examples of the work that has been carried out, and includes a fairly complete set of references, organized by problem studied.<\/jats:p>","DOI":"10.1145\/2993749.2993766","type":"journal-article","created":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T18:24:38Z","timestamp":1472754278000},"page":"93-129","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Online Algorithms with Advice: A Survey"],"prefix":"10.1145","volume":"47","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Kudahl","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper W.","family":"Mikkelsen","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"e_1_2_1_2_1","volume-title":"Reordering buffer management with advice. J. Sched","author":"Adamaszek Anna","year":"2016","unstructured":"Anna Adamaszek , Marc P. Renault , Adi Ros\u00e9n , and Rob van Stee . Reordering buffer management with advice. J. Sched ., 2016 . Preliminary version in WAOA '13. doi:10.1007\/s10951-016-0487-8. 10.1007\/s10951-016-0487-8 Anna Adamaszek, Marc P. Renault, Adi Ros\u00e9n, and Rob van Stee. Reordering buffer management with advice. J. Sched., 2016. Preliminary version in WAOA'13. doi:10.1007\/s10951-016-0487-8."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.031"},{"key":"e_1_2_1_4_1","series-title":"LNCS","first-page":"13","volume-title":"SWAT","author":"Albers Susanne","year":"2014","unstructured":"Susanne Albers and Matthias Hellwig . Online makespan minimization with parallel schedules . In SWAT , volume 8503 of LNCS , pages 13 -- 25 , 2014 . doi:10.1007\/978-3-319-08404-6_2. 10.1007\/978-3-319-08404-6_2 Susanne Albers and Matthias Hellwig. Online makespan minimization with parallel schedules. In SWAT, volume 8503 of LNCS, pages 13--25, 2014. doi:10.1007\/978-3-319-08404-6_2."},{"key":"e_1_2_1_5_1","series-title":"LNCS","first-page":"40","volume-title":"WADS","author":"Angelopoulos Spyros","year":"2015","unstructured":"Spyros Angelopoulos , Christoph D\u00fcrr , Shahin Kamali , Marc P. Renault , and Adi Ros\u00e9n . Online bin packing with advice of small size . In WADS , volume 9214 of LNCS , pages 40 -- 53 , 2015 . doi:10.1007\/978-3-319-21840-3_4. 10.1007\/978-3-319-21840-3_4 Spyros Angelopoulos, Christoph D\u00fcrr, Shahin Kamali, Marc P. Renault, and Adi Ros\u00e9n. Online bin packing with advice of small size. In WADS, volume 9214 of LNCS, pages 40--53, 2015. doi:10.1007\/978-3-319-21840-3_4."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"Arora Sanjeev","year":"2009","unstructured":"Sanjeev Arora and Boaz Barak . Computational Complexity: A Modern Approach . Cambridge University Press , 2009 . Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/647907.739828"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00258-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.04.017"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783434"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90209-E"},{"key":"e_1_2_1_12_1","series-title":"LNCS","first-page":"77","volume-title":"SOFSEM","author":"Barhum Kfir","year":"2014","unstructured":"Kfir Barhum . Tight bounds for the advice complexity of the online minimum Steiner tree problem . In SOFSEM , volume 8327 of LNCS , pages 77 -- 88 , 2014 . doi:10.1007\/978-3-319-04298-5_8. 10.1007\/978-3-319-04298-5_8 Kfir Barhum. Tight bounds for the advice complexity of the online minimum Steiner tree problem. In SOFSEM, volume 8327 of LNCS, pages 77--88, 2014. doi:10.1007\/978-3-319-04298-5_8."},{"key":"e_1_2_1_13_1","series-title":"LNCS","first-page":"89","volume-title":"SOFSEM","author":"Barhum Kfir","year":"2014","unstructured":"Kfir Barhum , Hans-Joachim B\u00f6ckenhauer , Michal Fori\u0161ek , Heidi Gebauer , Juraj Hromkovi\u010d , Sacha Krug , Jasmin Smula , and Bj\u00f6rn Steffen . On the power of advice and randomization for the disjoint path allocation problem . In SOFSEM , volume 8327 of LNCS , pages 89 -- 101 , 2014 . doi:10.1007\/978-3-319-04298-5_9. 10.1007\/978-3-319-04298-5_9 Kfir Barhum, Hans-Joachim B\u00f6ckenhauer, Michal Fori\u0161ek, Heidi Gebauer, Juraj Hromkovi\u010d, Sacha Krug, Jasmin Smula, and Bj\u00f6rn Steffen. On the power of advice and randomization for the disjoint path allocation problem. In SOFSEM, volume 8327 of LNCS, pages 89--101, 2014. doi:10.1007\/978-3-319-04298-5_9."},{"key":"e_1_2_1_14_1","volume-title":"Deterministic graph exploration with advice. ArXiv","author":"Barun Gorain Andrzej Pelc","year":"2016","unstructured":"Andrzej Pelc Barun Gorain . Deterministic graph exploration with advice. ArXiv , 2016 . arXiv:1607.01657 {cs.DS}. URL : http:\/\/arxiv.org\/abs\/1607.01657. Andrzej Pelc Barun Gorain. Deterministic graph exploration with advice. ArXiv, 2016. arXiv:1607.01657 {cs.DS}. URL: http:\/\/arxiv.org\/abs\/1607.01657."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100268"},{"key":"e_1_2_1_17_1","series-title":"LNCS","first-page":"195","volume-title":"SOFSEM","author":"Bianchi Maria Paola","year":"2016","unstructured":"Maria Paola Bianchi , Hans-Joachim B\u00f6ckenhauer , Tatjana Br\u00fclisauer , Dennis Komm , and Beatrice Palano . Online minimum spanning tree with advice . In SOFSEM , volume 9587 of LNCS , pages 195 -- 207 , 2016 . doi:10.1007\/978-3-662-49192-8_16. 10.1007\/978-3-662-49192-8_16 Maria Paola Bianchi, Hans-Joachim B\u00f6ckenhauer, Tatjana Br\u00fclisauer, Dennis Komm, and Beatrice Palano. Online minimum spanning tree with advice. In SOFSEM, volume 9587 of LNCS, pages 195--207, 2016. doi:10.1007\/978-3-662-49192-8_16."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9819-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.027"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007621832648"},{"key":"e_1_2_1_21_1","series-title":"LNCS","first-page":"747","volume-title":"COCOON","author":"B\u00f6ckenhauer Hans-Joachim","year":"2015","unstructured":"Hans-Joachim B\u00f6ckenhauer , Richard Dobson , Sacha Krug , and Kathleen Steinh\u00f6fel . On energy-efficient computations with advice . In COCOON , volume 9198 of LNCS , pages 747 -- 758 , 2015 . doi:10.1007\/ 978-3-319-21398-9_58. Hans-Joachim B\u00f6ckenhauer, Richard Dobson, Sacha Krug, and Kathleen Steinh\u00f6fel. On energy-efficient computations with advice. In COCOON, volume 9198 of LNCS, pages 747--758, 2015. doi:10.1007\/ 978-3-319-21398-9_58."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13350-8_20"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.006"},{"key":"e_1_2_1_24_1","series-title":"LNCS","first-page":"207","volume-title":"ICALP (1)","author":"B\u00f6ckenhauer Hans-Joachim","year":"2011","unstructured":"Hans-Joachim B\u00f6ckenhauer , Dennis Komm , Rastislav Kr\u00e1lovi\u010d , and Richard Kr\u00e1lovi\u010d . On the advice complexity of the k-server problem . In ICALP (1) , volume 6755 of LNCS , pages 207 -- 218 , 2011 . doi:10.1007\/978-3-642-22006-7_18. 10.1007\/978-3-642-22006-7_18 Hans-Joachim B\u00f6ckenhauer, Dennis Komm, Rastislav Kr\u00e1lovi\u010d, and Richard Kr\u00e1lovi\u010d. On the advice complexity of the k-server problem. In ICALP (1), volume 6755 of LNCS, pages 207--218, 2011. doi:10.1007\/978-3-642-22006-7_18."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_35"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.01.027"},{"key":"e_1_2_1_27_1","series-title":"CEUR Workshop Proceedings","first-page":"1","volume-title":"Student Research Forum Papers and Posters at SOFSEM","author":"B\u00f6hm Martin","year":"2016","unstructured":"Martin B\u00f6hm . Lower bounds for online bin stretching with several bins . In Student Research Forum Papers and Posters at SOFSEM , volume 1548 of CEUR Workshop Proceedings , pages 1 -- 12 , 2016 . URL : http:\/\/ceur-ws.org\/Vol-1548\/001-Bohm.pdf. Martin B\u00f6hm. Lower bounds for online bin stretching with several bins. In Student Research Forum Papers and Posters at SOFSEM, volume 1548 of CEUR Workshop Proceedings, pages 1--12, 2016. URL: http:\/\/ceur-ws.org\/Vol-1548\/001-Bohm.pdf."},{"key":"e_1_2_1_28_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","year":"1998","unstructured":"Allan Borodin and Ran El-Yaniv . Online Computation and Competitive Analysis . Cambridge University Press , 1998 . Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-34171-2_10"},{"key":"e_1_2_1_31_1","series-title":"LIPIcs","first-page":"116","volume-title":"STACS","author":"Boyar Joan","year":"2015","unstructured":"Joan Boyar , Lene M. Favrholdt , Christian Kudahl , and Jesper W. Mikkelsen . Advice complexity for a class of online problems . In STACS , volume 30 of LIPIcs , pages 116 -- 129 , 2015 . Full paper to appear in Theor. Comput. Syst. doi:10.4230\/LIPIcs.STACS.2015.116. 10.4230\/LIPIcs.STACS.2015.116 Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. Advice complexity for a class of online problems. In STACS, volume 30 of LIPIcs, pages 116--129, 2015. Full paper to appear in Theor. Comput. Syst. doi:10.4230\/LIPIcs.STACS.2015.116."},{"key":"e_1_2_1_32_1","volume-title":"LNCS","author":"Boyar Joan","year":"2016","unstructured":"Joan Boyar , Lene M. Favrholdt , Christian Kudahl , and Jesper W. Mikkelsen . Weighted online problems with advice. In IWOCA , LNCS , 2016 . To appear. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. Weighted online problems with advice. In IWOCA, LNCS, 2016. To appear."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9884-6"},{"key":"e_1_2_1_34_1","series-title":"LNCS","first-page":"210","volume-title":"LATA","author":"Boyar Joan","year":"2014","unstructured":"Joan Boyar , Shahin Kamali , Kim S. Larsen , and Alejandro L\u00f3pez-Ortiz . On the list update problem with advice . In LATA , volume 8370 of LNCS , pages 210 -- 221 , 2014 . Full paper to appear in Inform. Comput. doi:10.1007\/978-3-319-04921-2_17. 10.1007\/978-3-319-04921-2_17 Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro L\u00f3pez-Ortiz. On the list update problem with advice. In LATA, volume 8370 of LNCS, pages 210--221, 2014. Full paper to appear in Inform. Comput. doi:10.1007\/978-3-319-04921-2_17."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9955-8"},{"key":"e_1_2_1_36_1","series-title":"LNCS","first-page":"229","volume-title":"SOFSEM","author":"Burjons Elisabet","year":"2016","unstructured":"Elisabet Burjons , Juraj Hromkovi\u010d , Xavier Mu\u00f1oz , and Walter Unger . Online graph coloring with advice and randomized adversary . In SOFSEM , volume 9587 of LNCS , pages 229 -- 240 , 2016 . doi:10.1007\/978-3-662-49192-8_19. 10.1007\/978-3-662-49192-8_19 Elisabet Burjons, Juraj Hromkovi\u010d, Xavier Mu\u00f1oz, and Walter Unger. Online graph coloring with advice and randomized adversary. In SOFSEM, volume 9587 of LNCS, pages 229--240, 2016. doi:10.1007\/978-3-662-49192-8_19."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9279-2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.06.044"},{"key":"e_1_2_1_40_1","volume-title":"LNCS","author":"Clemente Jhoirene","year":"2016","unstructured":"Jhoirene Clemente , Christian Kudahl , Dennis Komm , and Juraj Hromkovi\u010d . Advice complexity of the online search problem. In IWOCA , LNCS , 2016 . To appear. Jhoirene Clemente, Christian Kudahl, Dennis Komm, and Juraj Hromkovi\u010d. Advice complexity of the online search problem. In IWOCA, LNCS, 2016. To appear."},{"key":"e_1_2_1_41_1","volume-title":"Elements of Information Theory","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A. Thomas . Elements of Information Theory . Wiley , 2 nd edition, 2006 . doi:10.1002\/047174882X. 10.1002\/047174882X Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, 2nd edition, 2006. doi:10.1002\/047174882X.","edition":"2"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9592-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31104-8_23"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2009012"},{"key":"e_1_2_1_45_1","series-title":"LNCS","first-page":"177","volume-title":"SOFSEM","author":"Dohrau J\u00e9r\u00f4me","year":"2015","unstructured":"J\u00e9r\u00f4me Dohrau . Online makespan scheduling with sublinear advice . In SOFSEM , volume 8939 of LNCS , pages 177 -- 188 , 2015 . doi:10.1007\/978-3-662-46078-8_15. 10.1007\/978-3-662-46078-8_15 J\u00e9r\u00f4me Dohrau. Online makespan scheduling with sublinear advice. In SOFSEM, volume 8939 of LNCS, pages 177--188, 2015. doi:10.1007\/978-3-662-46078-8_15."},{"key":"e_1_2_1_46_1","series-title":"LNCS","first-page":"136","volume-title":"ISAAC","author":"Dorrigiv Reza","year":"2012","unstructured":"Reza Dorrigiv , Meng He , and Norbert Zeh . On the advice complexity of bu?er management . In ISAAC , volume 7676 of LNCS , pages 136 -- 145 , 2012 . doi:10.1007\/978-3-642-35261-4_17. 10.1007\/978-3-642-35261-4_17 Reza Dorrigiv, Meng He, and Norbert Zeh. On the advice complexity of bu?er management. In ISAAC, volume 7676 of LNCS, pages 136--145, 2012. doi:10.1007\/978-3-642-35261-4_17."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086649.1086670"},{"key":"e_1_2_1_48_1","volume-title":"LIPIcs","author":"D\u00fcrr Christoph","year":"2016","unstructured":"Christoph D\u00fcrr , Christian Konrad , and Marc P. Renault . On the power of advice and randomization for online bipartite matching. In ESA , LIPIcs , 2016 . To appear. Full version in arXiv:1602.07154 {cs.DS}. URL: https:\/\/arxiv.org\/abs\/1602.07154. Christoph D\u00fcrr, Christian Konrad, and Marc P. Renault. On the power of advice and randomization for online bipartite matching. In ESA, LIPIcs, 2016. To appear. Full version in arXiv:1602.07154 {cs.DS}. URL: https:\/\/arxiv.org\/abs\/1602.07154."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-009-0119-7"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.007"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/647910.740462"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28332-1_20"},{"key":"e_1_2_1_55_1","volume-title":"Advice complexity of online graph coloring. Unpublished manuscript","author":"Fori\u0161ek Michal","year":"2012","unstructured":"Michal Fori\u0161ek , Lucia Keller , and Monika Steinov\u00e1 . Advice complexity of online graph coloring. Unpublished manuscript , 2012 . URL : http:\/\/people.ksp.sk\/~misof\/junk\/chwd.pdf. Michal Fori\u0161ek, Lucia Keller, and Monika Steinov\u00e1. Advice complexity of online graph coloring. Unpublished manuscript, 2012. URL: http:\/\/people.ksp.sk\/~misof\/junk\/chwd.pdf."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.005"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.07.002"},{"key":"e_1_2_1_58_1","series-title":"LNCS","first-page":"417","volume-title":"COCOON","author":"Gebauer Heidi","year":"2015","unstructured":"Heidi Gebauer , Dennis Komm , Rastislav Kr\u00e1lovi\u010d , Richard Kr\u00e1lovi\u010d , and Jasmin Smula . Disjoint path allocation with sublinear advice . In COCOON , volume 9198 of LNCS , pages 417 -- 429 , 2015 . doi:10.1007\/978-3-319-21398-9_33. 10.1007\/978-3-319-21398-9_33 Heidi Gebauer, Dennis Komm, Rastislav Kr\u00e1lovi\u010d, Richard Kr\u00e1lovi\u010d, and Jasmin Smula. Disjoint path allocation with sublinear advice. In COCOON, volume 9198 of LNCS, pages 417--429, 2015. doi:10.1007\/978-3-319-21398-9_33."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_60_1","series-title":"LNCS","first-page":"55","volume-title":"SIROCCO","author":"Gupta Sushmita","year":"2013","unstructured":"Sushmita Gupta , Shahin Kamali , and Alejandro L\u00f3pez-Ortiz . On advice complexity of the k-server problem under sparse metrics . In SIROCCO , volume 8179 of LNCS , pages 55 -- 67 , 2013 . doi:10.1007\/978-3-319-03578-9_5. 10.1007\/978-3-319-03578-9_5 Sushmita Gupta, Shahin Kamali, and Alejandro L\u00f3pez-Ortiz. On advice complexity of the k-server problem under sparse metrics. In SIROCCO, volume 8179 of LNCS, pages 55--67, 2013. doi:10.1007\/978-3-319-03578-9_5."},{"key":"e_1_2_1_61_1","series-title":"LNCS","first-page":"507","volume-title":"ISAAC","author":"Gutowski Grzegorz","year":"2014","unstructured":"Grzegorz Gutowski , Jakub Kozik , Piotr Micek , and Xuding Zhu . Lower bounds for on-line graph colorings . In ISAAC , volume 8889 of LNCS , pages 507 -- 515 , 2014 . doi:10.1007\/978-3-319-13075-0_40. 10.1007\/978-3-319-13075-0_40 Grzegorz Gutowski, Jakub Kozik, Piotr Micek, and Xuding Zhu. Lower bounds for on-line graph colorings. In ISAAC, volume 8889 of LNCS, pages 507--515, 2014. doi:10.1007\/978-3-319-13075-0_40."},{"key":"e_1_2_1_62_1","volume-title":"First fit and on-line chromatic number of families of graphs. Ars Combinatoria, 29(C):168--176","author":"Gy\u00e1rf\u00e1s Andr\u00e1s","year":"1990","unstructured":"Andr\u00e1s Gy\u00e1rf\u00e1s and Jen\u00f6 Lehel . First fit and on-line chromatic number of families of graphs. Ars Combinatoria, 29(C):168--176 , 1990 . Andr\u00e1s Gy\u00e1rf\u00e1s and Jen\u00f6 Lehel. First fit and on-line chromatic number of families of graphs. Ars Combinatoria, 29(C):168--176, 1990."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120212"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00411-X"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90157-0"},{"key":"e_1_2_1_66_1","volume-title":"LIPIcs","author":"Heydrich Sandy","year":"2016","unstructured":"Sandy Heydrich and Rob van Stee . Beating the harmonic lower bound for online bin packing. In ICALP , LIPIcs , 2016 . To appear. Full version in arXiv:1511.00876 {cs.DS}. URL: http:\/\/arxiv.org\/abs\/1511.00876. Sandy Heydrich and Rob van Stee. Beating the harmonic lower bound for online bin packing. In ICALP, LIPIcs, 2016. To appear. Full version in arXiv:1511.00876 {cs.DS}. URL: http:\/\/arxiv.org\/abs\/1511.00876."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_68_1","series-title":"LNCS","first-page":"24","volume-title":"MFCS","author":"Hromkovi\u010d Juraj","year":"2010","unstructured":"Juraj Hromkovi\u010d , Rastislav Kr\u00e1lovi\u010d , and Richard Kr\u00e1lovi\u010d . Information complexity of online problems . In MFCS , volume 6281 of LNCS , pages 24 -- 36 , 2010 . doi:10.1007\/978-3-642-15155-2_3. 10.1007\/978-3-642-15155-2_3 Juraj Hromkovi\u010d, Rastislav Kr\u00e1lovi\u010d, and Richard Kr\u00e1lovi\u010d. Information complexity of online problems. In MFCS, volume 6281 of LNCS, pages 24--36, 2010. doi:10.1007\/978-3-642-15155-2_3."},{"issue":"4","key":"e_1_2_1_69_1","first-page":"185","article-title":"Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times","volume":"5","author":"Huang Yikun","year":"2010","unstructured":"Yikun Huang and Yong Wu . Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times . International Mathematical Forum , 5 ( 4 ): 185 -- 190 , 2010 . URL: http:\/\/www.m-hikari.com\/imf-2010\/1-4-2010\/wuyongIMF1-4-2010.pdf. Yikun Huang and Yong Wu. Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times. International Mathematical Forum, 5(4):185--190, 2010. URL: http:\/\/www.m-hikari.com\/imf-2010\/1-4-2010\/wuyongIMF1-4-2010.pdf.","journal-title":"International Mathematical Forum"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-007-0058-8"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90155-4"},{"key":"e_1_2_1_72_1","first-page":"162","volume-title":"The Canadian Conference on Computational Geometry","author":"Kamali Shahin","year":"2014","unstructured":"Shahin Kamali and Alejandro L\u00f3pez-Ortiz . Almost online square packing . In The Canadian Conference on Computational Geometry , pages 162 -- 168 , 2014 . URL: http:\/\/www.cccg.ca\/proceedings\/2014\/papers\/paper24.pdf. Shahin Kamali and Alejandro L\u00f3pez-Ortiz. Almost online square packing. In The Canadian Conference on Computational Geometry, pages 162--168, 2014. URL: http:\/\/www.cccg.ca\/proceedings\/2014\/papers\/paper24.pdf."},{"key":"e_1_2_1_73_1","first-page":"372","volume-title":"Data Compression Conference","author":"Kamali Shahin","year":"2014","unstructured":"Shahin Kamali and Alejandro L\u00f3pez-Ortiz . Better compression through better list update algorithms . In Data Compression Conference , pages 372 -- 381 , 2014 . doi:10.1109\/DCC.2014.86. 10.1109\/DCC.2014.86 Shahin Kamali and Alejandro L\u00f3pez-Ortiz. Better compression through better list update algorithms. In Data Compression Conference, pages 372--381, 2014. doi:10.1109\/DCC.2014.86."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.14"},{"key":"e_1_2_1_75_1","volume-title":"ETHZ\u00fcrich","author":"Keller Lucia","year":"2014","unstructured":"Lucia Keller . Complexity of optimization problems, advice and approximation. PhDthesis , ETHZ\u00fcrich , 2014 . doi:10.3929\/ethz-a-010143463. 10.3929\/ethz-a-010143463 Lucia Keller. Complexity of optimization problems, advice and approximation. PhDthesis, ETHZ\u00fcrich, 2014. doi:10.3929\/ethz-a-010143463."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-015-0430-4"},{"key":"e_1_2_1_77_1","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BFb0029574","volume-title":"Online Algorithms -- The State of the Art","author":"Kierstead Hal A.","year":"1998","unstructured":"Hal A. Kierstead . Coloring graphs online . In Online Algorithms -- The State of the Art , pages 281 -- 305 . Springer , 1998 . doi:10.1007\/BFb0029574. 10.1007\/BFb0029574 Hal A. Kierstead. Coloring graphs online. In Online Algorithms -- The State of the Art, pages 281--305. Springer, 1998. doi:10.1007\/BFb0029574."},{"key":"e_1_2_1_78_1","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"85","volume-title":"On-Line Algorithms","author":"Kierstead Hal A.","year":"1991","unstructured":"Hal A. Kierstead and William T. Trotter . On-line graph coloring . In On-Line Algorithms , volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science , pages 85 -- 92 . DIMACS\/AMS , 1991 . Hal A. Kierstead and William T. Trotter. On-line graph coloring. In On-Line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 85--92. DIMACS\/AMS, 1991."},{"key":"e_1_2_1_79_1","volume-title":"LIPIcs","author":"Komm Dennis","year":"2016","unstructured":"Dennis Komm , Rastislav Kr\u00e1lovi\u010d , Richard Kr\u00e1lovi\u010d , and Christian Kudahl . Advice complexity of the online induced subgraph problem. In MFCS , LIPIcs , 2016 . To appear. Full version in arXiv:1512.05996 {cs.CC}. URL: http:\/\/arxiv.org\/abs\/1512.05996. Dennis Komm, Rastislav Kr\u00e1lovi\u010d, Richard Kr\u00e1lovi\u010d, and Christian Kudahl. Advice complexity of the online induced subgraph problem. In MFCS, LIPIcs, 2016. To appear. Full version in arXiv:1512.05996 {cs.CC}. URL: http:\/\/arxiv.org\/abs\/1512.05996."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25258-2_23"},{"issue":"2","key":"e_1_2_1_81_1","first-page":"249","article-title":"Advice complexity and barely random algorithms. RAIRO - Theor","volume":"45","author":"Komm Dennis","year":"2011","unstructured":"Dennis Komm and Richard Kr\u00e1lovi\u010d . Advice complexity and barely random algorithms. RAIRO - Theor . Inf. Appl. , 45 ( 2 ): 249 -- 267 , 2011 . Preliminary version in SOFSEM'11. doi:10.1051\/ita\/2011105. 10.1051\/ita Dennis Komm and Richard Kr\u00e1lovi\u010d. Advice complexity and barely random algorithms. RAIRO - Theor. Inf. Appl., 45(2):249--267, 2011. Preliminary version in SOFSEM'11. doi:10.1051\/ita\/2011105.","journal-title":"Inf. Appl."},{"key":"e_1_2_1_82_1","series-title":"LNCS","first-page":"241","volume-title":"CSR","author":"Komm Dennis","year":"2012","unstructured":"Dennis Komm , Richard Kr\u00e1lovi\u010d , and Tobias M\u00f6mke . On the advice complexity of the set cover problem . In CSR , volume 7353 of LNCS , pages 241 -- 252 , 2012 . doi:10.1007\/978-3-642-30642-6_23. 10.1007\/978-3-642-30642-6_23 Dennis Komm, Richard Kr\u00e1lovi\u010d, and Tobias M\u00f6mke. On the advice complexity of the set cover problem. In CSR, volume 7353 of LNCS, pages 241--252, 2012. doi:10.1007\/978-3-642-30642-6_23."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.002"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"e_1_2_1_85_1","series-title":"LNCS","first-page":"21","volume-title":"SOFSEM","author":"Kr\u00e1lovi\u010d Rastislav","year":"2014","unstructured":"Rastislav Kr\u00e1lovi\u010d . Advice complexity: Quantitative approach to a-priori information . In SOFSEM , volume 8327 of LNCS , pages 21 -- 29 , 2014 . doi:10.1007\/978-3-319-04298-5_3. 10.1007\/978-3-319-04298-5_3 Rastislav Kr\u00e1lovi\u010d. Advice complexity: Quantitative approach to a-priori information. In SOFSEM, volume 8327 of LNCS, pages 21--29, 2014. doi:10.1007\/978-3-319-04298-5_3."},{"issue":"2","key":"e_1_2_1_86_1","first-page":"139","article-title":"Towards using the history in online computation with advice. RAIRO - Theor","volume":"49","author":"Krug Sacha","year":"2015","unstructured":"Sacha Krug . Towards using the history in online computation with advice. RAIRO - Theor . Inf. Appl. , 49 ( 2 ): 139 -- 152 , 2015 . doi:10.1051\/ita\/2015003. 10.1051\/ita Sacha Krug. Towards using the history in online computation with advice. RAIRO - Theor. Inf. Appl., 49(2):139--152, 2015. doi:10.1051\/ita\/2015003.","journal-title":"Inf. Appl."},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585758"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.034"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18173-8_26"},{"key":"e_1_2_1_91_1","volume-title":"LIPIcs","author":"Mikkelsen Jesper W.","year":"2016","unstructured":"Jesper W. Mikkelsen . Randomization can be as helpful as a glimpse of the future in online computation. In ICALP , LIPIcs , 2016 . To appear. Full version in arXiv:1511.05886 {cs.DS}. URL: http:\/\/arxiv.org\/abs\/1511.05886. Jesper W. Mikkelsen. Randomization can be as helpful as a glimpse of the future in online computation. In ICALP, LIPIcs, 2016. To appear. Full version in arXiv:1511.05886 {cs.DS}. URL: http:\/\/arxiv.org\/abs\/1511.05886."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.06.013"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9434-z"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.050"},{"key":"e_1_2_1_97_1","series-title":"LNCS","first-page":"345","volume-title":"CIAC","author":"Seibert Sebastian","year":"2013","unstructured":"Sebastian Seibert , Andreas Sprock , and Walter Unger . Advice complexity of the online coloring problem . In CIAC , volume 7878 of LNCS , pages 345 -- 357 , 2013 . doi:10.1007\/978-3-642-38233-8_29. 10.1007\/978-3-642-38233-8_29 Sebastian Seibert, Andreas Sprock, and Walter Unger. Advice complexity of the online coloring problem. In CIAC, volume 7878 of LNCS, pages 345--357, 2013. doi:10.1007\/978-3-642-38233-8_29."},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(00)00053-5"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.015"},{"key":"e_1_2_1_103_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","year":"2003","unstructured":"Vijay V. Vazirani . Approximation Algorithms . Springer , 2003 . doi:10.1007\/978-3-662-04565-7. 10.1007\/978-3-662-04565-7 Vijay V. Vazirani. Approximation Algorithms. Springer, 2003. doi:10.1007\/978-3-662-04565-7."},{"key":"e_1_2_1_104_1","first-page":"9","article-title":"Critical graphs with given chromatic class","volume":"5","author":"Vizing Vadim G.","year":"1965","unstructured":"Vadim G. Vizing . Critical graphs with given chromatic class . Metody Diskret. Analiz. , 5 : 9 -- 17 , 1965 . In Russian. Vadim G. Vizing. Critical graphs with given chromatic class. Metody Diskret. Analiz., 5:9--17, 1965. In Russian.","journal-title":"Metody Diskret. Analiz."},{"key":"e_1_2_1_105_1","series-title":"LNCS","first-page":"147","volume-title":"MEMICS","author":"Wehner David","year":"2014","unstructured":"David Wehner . A new concept in advice complexity of job shop scheduling . In MEMICS , volume 8934 of LNCS , pages 147 -- 158 , 2014 . doi:10.1007\/978-3-319-14896-0_13. 10.1007\/978-3-319-14896-0_13 David Wehner. A new concept in advice complexity of job shop scheduling. In MEMICS, volume 8934 of LNCS, pages 147--158, 2014. doi:10.1007\/978-3-319-14896-0_13."},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18173-8_31"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.01.003"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08016-1_29"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2993749.2993766","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2993749.2993766","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:24Z","timestamp":1750218624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2993749.2993766"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,31]]},"references-count":105,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,8,31]]}},"alternative-id":["10.1145\/2993749.2993766"],"URL":"https:\/\/doi.org\/10.1145\/2993749.2993766","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2016,8,31]]},"assertion":[{"value":"2016-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}