{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T16:39:19Z","timestamp":1779295159211,"version":"3.51.4"},"reference-count":105,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,11]],"date-time":"2017-04-11T00:00:00Z","timestamp":1491868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Foundation","doi-asserted-by":"crossref","award":["VKR023219"],"award-info":[{"award-number":["VKR023219"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Danish Council for Independent Research, Natural Sciences","award":["DFF-1323-00247"],"award-info":[{"award-number":["DFF-1323-00247"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>In online scenarios requests arrive over time, and each request must be serviced in an irrevocable manner before the next request arrives. Online algorithms with advice is an area of research where one attempts to measure how much knowledge of future requests is necessary to achieve a given performance level, as defined by the competitive ratio. When this knowledge, the advice, is obtainable, this leads to practical algorithms, called semi-online algorithms. On the other hand, each negative result gives robust results about the limitations of a broad range of semi-online algorithms. This survey explains the models for online algorithms with advice, motivates the study in general, presents some examples of the work that has been carried out, and includes an extensive set of references, organized by problem studied.<\/jats:p>","DOI":"10.1145\/3056461","type":"journal-article","created":{"date-parts":[[2017,4,12]],"date-time":"2017-04-12T12:05:49Z","timestamp":1491998749000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Online Algorithms with Advice"],"prefix":"10.1145","volume":"50","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Kudahl","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0560-3794","authenticated-orcid":false,"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper W.","family":"Mikkelsen","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,4,11]]},"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","unstructured":"Anna Adamaszek Marc P. Renault Adi Ros\u00e9n and Rob van Stee. 2016. Reordering buffer management with advice. J. Sched. (2016). To appear. Preliminary version in WAOA\u201913.  Anna Adamaszek Marc P. Renault Adi Ros\u00e9n and Rob van Stee. 2016. Reordering buffer management with advice. J. Sched. (2016). To appear. Preliminary version in WAOA\u201913."},{"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","volume-title":"SWAT (LNCS)","author":"Albers Susanne","unstructured":"Susanne Albers and Matthias Hellwig . 2014. Online makespan minimization with parallel schedules . In SWAT (LNCS) , Vol. 8503 . Springer , 13--25. Susanne Albers and Matthias Hellwig. 2014. Online makespan minimization with parallel schedules. In SWAT (LNCS), Vol. 8503. Springer, 13--25."},{"key":"e_1_2_1_5_1","volume-title":"WADS (LNCS)","author":"Angelopoulos Spyros","unstructured":"Spyros Angelopoulos , Christoph D\u00fcrr , Shahin Kamali , Marc P. Renault , and Adi Ros\u00e9n . 2015. Online bin packing with advice of small size . In WADS (LNCS) , Vol. 9214 . Springer , 40--53. Spyros Angelopoulos, Christoph D\u00fcrr, Shahin Kamali, Marc P. Renault, and Adi Ros\u00e9n. 2015. Online bin packing with advice of small size. In WADS (LNCS), Vol. 9214. Springer, 40--53."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199808)1:2<67::AID-JOS6>3.0.CO;2-Y"},{"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","volume-title":"SOFSEM (LNCS)","author":"Barhum Kfir","unstructured":"Kfir Barhum . 2014. Tight bounds for the advice complexity of the online minimum steiner tree problem . In SOFSEM (LNCS) , Vol. 8327 . Springer , 77--88. Kfir Barhum. 2014. Tight bounds for the advice complexity of the online minimum steiner tree problem. In SOFSEM (LNCS), Vol. 8327. Springer, 77--88."},{"key":"e_1_2_1_13_1","volume-title":"SOFSEM (LNCS)","author":"Barhum Kfir","unstructured":"Kfir Barhum , Hans-Joachim B\u00f6ckenhauer , Michal Fori\u0161ek , Heidi Gebauer , Juraj Hromkovi\u010d , Sacha Krug , Jasmin Smula , and Bj\u00f6rn Steffen . 2014. On the power of advice and randomization for the disjoint path allocation problem . In SOFSEM (LNCS) , Vol. 8327 . Springer , 89--101. Kfir Barhum, Hans-Joachim B\u00f6ckenhauer, Michal Fori\u0161ek, Heidi Gebauer, Juraj Hromkovi\u010d, Sacha Krug, Jasmin Smula, and Bj\u00f6rn Steffen. 2014. On the power of advice and randomization for the disjoint path allocation problem. In SOFSEM (LNCS), Vol. 8327. Springer, 89--101."},{"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 . 2016. Deterministic graph exploration with advice. ArXiv ( 2016 ). http:\/\/arxiv.org\/abs\/1607.01657 arXiv:1607.01657 {cs.DS}. Andrzej Pelc Barun Gorain. 2016. Deterministic graph exploration with advice. ArXiv (2016). http:\/\/arxiv.org\/abs\/1607.01657 arXiv:1607.01657 {cs.DS}."},{"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.1007\/BF01294260"},{"key":"e_1_2_1_17_1","volume-title":"SOFSEM (LNCS)","author":"Bianchi Maria Paola","unstructured":"Maria Paola Bianchi , Hans-Joachim B\u00f6ckenhauer , Tatjana Br\u00fclisauer , Dennis Komm , and Beatrice Palano . 2016. Online minimum spanning tree with advice . In SOFSEM (LNCS) , Vol. 9587 . Springer , 195--207. Maria Paola Bianchi, Hans-Joachim B\u00f6ckenhauer, Tatjana Br\u00fclisauer, Dennis Komm, and Beatrice Palano. 2016. Online minimum spanning tree with advice. In SOFSEM (LNCS), Vol. 9587. Springer, 195--207."},{"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","volume-title":"COCOON (LNCS)","author":"B\u00f6ckenhauer Hans-Joachim","unstructured":"Hans-Joachim B\u00f6ckenhauer , Richard Dobson , Sacha Krug , and Kathleen Steinh\u00f6fel . 2015. On energy-efficient computations with advice . In COCOON (LNCS) , Vol. 9198 . Springer , 747--758. Hans-Joachim B\u00f6ckenhauer, Richard Dobson, Sacha Krug, and Kathleen Steinh\u00f6fel. 2015. On energy-efficient computations with advice. In COCOON (LNCS), Vol. 9198. Springer, 747--758."},{"key":"e_1_2_1_22_1","volume-title":"Computing with New Resources (LNCS), Vol.&nbsp;8808","author":"B\u00f6ckenhauer Hans-Joachim","unstructured":"Hans-Joachim B\u00f6ckenhauer , Juraj Hromkovi\u010d , and Dennis Komm . 2014a. A technique to obtain hardness results for randomized online algorithms\u2014A survey . In Computing with New Resources (LNCS), Vol.&nbsp;8808 . Springer , 264--276. Hans-Joachim B\u00f6ckenhauer, Juraj Hromkovi\u010d, and Dennis Komm. 2014a. A technique to obtain hardness results for randomized online algorithms\u2014A survey. In Computing with New Resources (LNCS), Vol.&nbsp;8808. Springer, 264--276."},{"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","volume-title":"ICALP (1) (LNCS)","author":"B\u00f6ckenhauer Hans-Joachim","unstructured":"Hans-Joachim B\u00f6ckenhauer , Dennis Komm , Rastislav Kr\u00e1lovi\u010d , and Richard Kr\u00e1lovi\u010d . 2011. On the advice complexity of the k-server problem . In ICALP (1) (LNCS) , Vol. 6755 . Springer , 207--218. Hans-Joachim B\u00f6ckenhauer, Dennis Komm, Rastislav Kr\u00e1lovi\u010d, and Richard Kr\u00e1lovi\u010d. 2011. On the advice complexity of the k-server problem. In ICALP (1) (LNCS), Vol. 6755. Springer, 207--218."},{"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","volume-title":"Student Research Forum Papers and Posters at SOFSEM (CEUR Workshop Proceedings)","author":"B\u00f6hm Martin","unstructured":"Martin B\u00f6hm . 2016. Lower bounds for online bin stretching with several bins . In Student Research Forum Papers and Posters at SOFSEM (CEUR Workshop Proceedings) , Vol. 1548 . RWTH Aachen University , 1--12. http:\/\/ceur-ws.org\/Vol-1548\/001-Bohm.pdf. Martin B\u00f6hm. 2016. Lower bounds for online bin stretching with several bins. In Student Research Forum Papers and Posters at SOFSEM (CEUR Workshop Proceedings), Vol. 1548. RWTH Aachen University, 1--12. 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","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"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","volume-title":"Mikkelsen","author":"Boyar Joan","year":"2015","unstructured":"Joan Boyar , Lene M. Favrholdt , Christian Kudahl , and Jesper W . Mikkelsen . 2015 a. Advice complexity for a class of online problems. In STACS (LIPIcs), Vol. 30 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 116--129. Full paper to appear in Theor. Comput. Syst. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. 2015a. Advice complexity for a class of online problems. In STACS (LIPIcs), Vol. 30. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 116--129. Full paper to appear in Theor. Comput. Syst."},{"key":"e_1_2_1_32_1","volume-title":"Mikkelsen","author":"Boyar Joan","year":"2016","unstructured":"Joan Boyar , Lene M. Favrholdt , Christian Kudahl , and Jesper W . Mikkelsen . 2016 b. Weighted online problems with advice. In IWOCA (LNCS), Vol. 9843 . Springer , 179--190. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. 2016b. Weighted online problems with advice. In IWOCA (LNCS), Vol. 9843. Springer, 179--190."},{"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","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.06.007"},{"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","volume-title":"SOFSEM (LNCS)","author":"Burjons Elisabet","unstructured":"Elisabet Burjons , Juraj Hromkovi\u010d , Xavier Mu\u00f1oz , and Walter Unger . 2016. Online graph coloring with advice and randomized adversary . In SOFSEM (LNCS) , Vol. 9587 . Springer , 229--240. Elisabet Burjons, Juraj Hromkovi\u010d, Xavier Mu\u00f1oz, and Walter Unger. 2016. Online graph coloring with advice and randomized adversary. In SOFSEM (LNCS), Vol. 9587. Springer, 229--240."},{"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":"IWOCA (LNCS)","author":"Clemente Jhoirene","unstructured":"Jhoirene Clemente , Juraj Hromkovi\u010d , Dennis Komm , and Christian Kudahl . 2016. Advice complexity of the online search problem . In IWOCA (LNCS) , Vol. 9843 . Springer , 203--212. Jhoirene Clemente, Juraj Hromkovi\u010d, Dennis Komm, and Christian Kudahl. 2016. Advice complexity of the online search problem. In IWOCA (LNCS), Vol. 9843. Springer, 203--212."},{"key":"e_1_2_1_41_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A . Thomas . 2006 . Elements of Information Theory (2nd ed.). Wiley . Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory (2nd ed.). Wiley."},{"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","volume-title":"SOFSEM (LNCS)","author":"Dohrau J\u00e9r\u00f4me","unstructured":"J\u00e9r\u00f4me Dohrau . 2015. Online makespan scheduling with sublinear advice . In SOFSEM (LNCS) , Vol. 8939 . Springer , 177--188. J\u00e9r\u00f4me Dohrau. 2015. Online makespan scheduling with sublinear advice. In SOFSEM (LNCS), Vol. 8939. Springer, 177--188."},{"key":"e_1_2_1_46_1","volume-title":"ISAAC (LNCS)","author":"Dorrigiv Reza","unstructured":"Reza Dorrigiv , Meng He , and Norbert Zeh . 2012. On the advice complexity of buffer management . In ISAAC (LNCS) , Vol. 7676 . Springer , 136--145. Reza Dorrigiv, Meng He, and Norbert Zeh. 2012. On the advice complexity of buffer management. In ISAAC (LNCS), Vol. 7676. Springer, 136--145."},{"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":"Renault","author":"D\u00fcrr Christoph","year":"2016","unstructured":"Christoph D\u00fcrr , Christian Konrad , and Marc P . Renault . 2016 . On the power of advice and randomization for online bipartite matching. In ESA (LIPIcs), Vol. 57 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik , 37:1--37:16. Christoph D\u00fcrr, Christian Konrad, and Marc P. Renault. 2016. On the power of advice and randomization for online bipartite matching. In ESA (LIPIcs), Vol. 57. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 37:1--37:16."},{"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","volume-title":"LATA (LNCS)","author":"Fori\u0161ek Michal","unstructured":"Michal Fori\u0161ek , Lucia Keller , and Monika Steinov\u00e1 . 2012. Advice complexity of online coloring for paths . In LATA (LNCS) , Vol. 7183 . Springer , 228--239. Michal Fori\u0161ek, Lucia Keller, and Monika Steinov\u00e1. 2012. Advice complexity of online coloring for paths. In LATA (LNCS), Vol. 7183. Springer, 228--239."},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Michal Fori\u0161ek Lucia Keller and Monika Steinov\u00e1. 2012. Advice complexity of online graph coloring. (2012). http:\/\/people.ksp.sk\/ misof\/junk\/chwd.pdf Unpublished manuscript.  Michal Fori\u0161ek Lucia Keller and Monika Steinov\u00e1. 2012. Advice complexity of online graph coloring. (2012). http:\/\/people.ksp.sk\/ misof\/junk\/chwd.pdf Unpublished manuscript.","DOI":"10.1007\/978-3-642-28332-1_20"},{"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","volume-title":"COCOON (LNCS)","author":"Gebauer Heidi","unstructured":"Heidi Gebauer , Dennis Komm , Rastislav Kr\u00e1lovi\u010d , Richard Kr\u00e1lovi\u010d , and Jasmin Smula . 2015. Disjoint path allocation with sublinear advice . In COCOON (LNCS) , Vol. 9198 . Springer , 417--429. Heidi Gebauer, Dennis Komm, Rastislav Kr\u00e1lovi\u010d, Richard Kr\u00e1lovi\u010d, and Jasmin Smula. 2015. Disjoint path allocation with sublinear advice. In COCOON (LNCS), Vol. 9198. Springer, 417--429."},{"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","volume-title":"SIROCCO (LNCS)","author":"Gupta Sushmita","unstructured":"Sushmita Gupta , Shahin Kamali , and Alejandro L\u00f3pez-Ortiz . 2013. On advice complexity of the k-server problem under sparse metrics . In SIROCCO (LNCS) , Vol. 8179 . Springer , 55--67. Sushmita Gupta, Shahin Kamali, and Alejandro L\u00f3pez-Ortiz. 2013. On advice complexity of the k-server problem under sparse metrics. In SIROCCO (LNCS), Vol. 8179. Springer, 55--67."},{"key":"e_1_2_1_61_1","volume-title":"ISAAC (LNCS)","author":"Gutowski Grzegorz","unstructured":"Grzegorz Gutowski , Jakub Kozik , Piotr Micek , and Xuding Zhu . 2014. Lower bounds for on-line graph colorings . In ISAAC (LNCS) , Vol. 8889 . Springer , 507--515. Grzegorz Gutowski, Jakub Kozik, Piotr Micek, and Xuding Zhu. 2014. Lower bounds for on-line graph colorings. In ISAAC (LNCS), Vol. 8889. Springer, 507--515."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120212"},{"key":"e_1_2_1_63_1","volume-title":"C","author":"Gy\u00e1rf\u00e1s Andr\u00e1s","year":"1990","unstructured":"Andr\u00e1s Gy\u00e1rf\u00e1s and Jen\u0151 Lehel . 1990. First fit and on-line chromatic number of families of graphs. Ars Combinatoria 29 , C ( 1990 ), 168--176. Andr\u00e1s Gy\u00e1rf\u00e1s and Jen\u0151 Lehel. 1990. First fit and on-line chromatic number of families of graphs. Ars Combinatoria 29, C (1990), 168--176."},{"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":"ICALP (LIPIcs)","volume":"55","author":"Heydrich Sandy","year":"2016","unstructured":"Sandy Heydrich and Rob van Stee . 2016 . Beating the harmonic lower bound for online bin packing . In ICALP (LIPIcs) , Vol. 55 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 41:1--41:14. Sandy Heydrich and Rob van Stee. 2016. Beating the harmonic lower bound for online bin packing. In ICALP (LIPIcs), Vol. 55. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 41:1--41:14."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_68_1","volume-title":"MFCS (LNCS)","author":"Hromkovi\u010d Juraj","unstructured":"Juraj Hromkovi\u010d , Rastislav Kr\u00e1lovi\u010d , and Richard Kr\u00e1lovi\u010d . 2010. Information complexity of online problems . In MFCS (LNCS) , Vol. 6281 . Springer , 24--36. Juraj Hromkovi\u010d, Rastislav Kr\u00e1lovi\u010d, and Richard Kr\u00e1lovi\u010d. 2010. Information complexity of online problems. In MFCS (LNCS), Vol. 6281. Springer, 24--36."},{"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 . 2010 . Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times . Int. Math. Forum 5 , 4 (2010), 185 -- 190 . http:\/\/www.m-hikari.com\/imf-2010\/1-4-2010\/wuyongIMF1-4-2010.pdf Yikun Huang and Yong Wu. 2010. Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times. Int. Math. Forum 5, 4 (2010), 185--190. http:\/\/www.m-hikari.com\/imf-2010\/1-4-2010\/wuyongIMF1-4-2010.pdf","journal-title":"Int. Math. 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","volume-title":"The Canadian Conference on Computational Geometry. www.cccg.ca, 162--168","author":"Kamali Shahin","year":"2014","unstructured":"Shahin Kamali and Alejandro L\u00f3pez-Ortiz . 2014 a. Almost online square packing . In The Canadian Conference on Computational Geometry. www.cccg.ca, 162--168 . Retrieved from http:\/\/www.cccg.ca\/proceedings\/ 2014\/papers\/paper24.pdf. Shahin Kamali and Alejandro L\u00f3pez-Ortiz. 2014a. Almost online square packing. In The Canadian Conference on Computational Geometry. www.cccg.ca, 162--168. Retrieved from http:\/\/www.cccg.ca\/proceedings\/2014\/papers\/paper24.pdf."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2014.86"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"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","volume-title":"Online Algorithms\u2014The State of the Art","author":"Kierstead Hal A.","unstructured":"Hal A. Kierstead . 1998. Coloring graphs online . In Online Algorithms\u2014The State of the Art . Springer , 281--305. Hal A. Kierstead. 1998. Coloring graphs online. In Online Algorithms\u2014The State of the Art. Springer, 281--305."},{"key":"e_1_2_1_78_1","volume-title":"Trotter","author":"Kierstead Hal A.","year":"1991","unstructured":"Hal A. Kierstead and William T . Trotter . 1991 . On-line graph coloring. In On-Line Algorithms (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), Vol. 7 . DIMACS\/AMS , 85--92. Hal A. Kierstead and William T. Trotter. 1991. On-line graph coloring. In On-Line Algorithms (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), Vol. 7. DIMACS\/AMS, 85--92."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011105"},{"key":"e_1_2_1_80_1","volume-title":"MFCS (LIPIcs)","volume":"58","author":"Komm Dennis","year":"2016","unstructured":"Dennis Komm , Rastislav Kr\u00e1lovi\u010d , Richard Kr\u00e1lovi\u010d , and Christian Kudahl . 2016 . Advice complexity of the online induced subgraph problem . In MFCS (LIPIcs) , Vol. 58 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 59:1--59:13. Dennis Komm, Rastislav Kr\u00e1lovi\u010d, Richard Kr\u00e1lovi\u010d, and Christian Kudahl. 2016. Advice complexity of the online induced subgraph problem. In MFCS (LIPIcs), Vol. 58. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 59:1--59:13."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25258-2_23"},{"key":"e_1_2_1_82_1","volume-title":"CSR (LNCS)","author":"Komm Dennis","unstructured":"Dennis Komm , Richard Kr\u00e1lovi\u010d , and Tobias M\u00f6mke . 2012. On the advice complexity of the set cover problem . In CSR (LNCS) , Vol. 7353 . Springer , 241--252. Dennis Komm, Richard Kr\u00e1lovi\u010d, and Tobias M\u00f6mke. 2012. On the advice complexity of the set cover problem. In CSR (LNCS), Vol. 7353. Springer, 241--252."},{"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","volume-title":"SOFSEM (LNCS)","author":"Kr\u00e1lovi\u010d Rastislav","unstructured":"Rastislav Kr\u00e1lovi\u010d . 2014. Advice complexity: Quantitative approach to A-priori information . In SOFSEM (LNCS) , Vol. 8327 . Springer , 21--29. Rastislav Kr\u00e1lovi\u010d. 2014. Advice complexity: Quantitative approach to A-priori information. In SOFSEM (LNCS), Vol. 8327. Springer, 21--29."},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2015003"},{"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":"ICALP (LIPIcs)","volume":"55","author":"Mikkelsen Jesper W.","year":"2016","unstructured":"Jesper W. Mikkelsen . 2016 . Randomization can be as helpful as a glimpse of the future in online computation . In ICALP (LIPIcs) , Vol. 55 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 39:1--39:14. Jesper W. Mikkelsen. 2016. Randomization can be as helpful as a glimpse of the future in online computation. In ICALP (LIPIcs), Vol. 55. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 39:1--39:14."},{"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":"crossref","unstructured":"Marc P. Renault. 2016. Online algorithms with advice for the dual bin packing problem. Cent. Eur. J. Oper. Res. (2016). To appear.  Marc P. Renault. 2016. Online algorithms with advice for the dual bin packing problem. Cent. Eur. J. Oper. Res. (2016). To appear.","DOI":"10.1007\/s10100-016-0450-y"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9434-z"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.050"},{"key":"e_1_2_1_98_1","volume-title":"CIAC (LNCS)","author":"Seibert Sebastian","unstructured":"Sebastian Seibert , Andreas Sprock , and Walter Unger . 2013. Advice complexity of the online coloring problem . In CIAC (LNCS) , Vol. 7878 . Springer , 345--357. Sebastian Seibert, Andreas Sprock, and Walter Unger. 2013. Advice complexity of the online coloring problem. In CIAC (LNCS), Vol. 7878. Springer, 345--357."},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(00)00053-5"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.015"},{"key":"e_1_2_1_104_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","unstructured":"Vijay V. Vazirani . 2003. Approximation Algorithms . Springer . Vijay V. Vazirani. 2003. Approximation Algorithms. Springer."},{"key":"e_1_2_1_105_1","first-page":"9","article-title":"Critical graphs with given chromatic class","volume":"5","author":"Vizing Vadim G.","year":"1965","unstructured":"Vadim G. Vizing . 1965 . Critical graphs with given chromatic class . Metody Diskret. Analiz. 5 (1965), 9 -- 17 . In Russian. Vadim G. Vizing. 1965. Critical graphs with given chromatic class. Metody Diskret. Analiz. 5 (1965), 9--17. In Russian.","journal-title":"Metody Diskret. Analiz."},{"key":"e_1_2_1_106_1","volume-title":"MEMICS (LNCS)","author":"Wehner David","unstructured":"David Wehner . 2014. A new concept in advice complexity of job shop scheduling . In MEMICS (LNCS) , Vol. 8934 . Springer , 147--158. David Wehner. 2014. A new concept in advice complexity of job shop scheduling. In MEMICS (LNCS), Vol. 8934. Springer, 147--158."},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18173-8_31"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.01.003"},{"key":"e_1_2_1_110_1","volume-title":"Frontiers in Algorithmics (LNCS)","author":"Zhao Xiaofan","unstructured":"Xiaofan Zhao and Hong Shen . 2014. On the advice complexity of one-dimensional online bin packing . In Frontiers in Algorithmics (LNCS) , Vol. 8497 . Springer , 320--329. Xiaofan Zhao and Hong Shen. 2014. On the advice complexity of one-dimensional online bin packing. In Frontiers in Algorithmics (LNCS), Vol. 8497. Springer, 320--329."}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3056461","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3056461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:13Z","timestamp":1750215793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3056461"}},"subtitle":["A Survey"],"short-title":[],"issued":{"date-parts":[[2017,4,11]]},"references-count":105,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3056461"],"URL":"https:\/\/doi.org\/10.1145\/3056461","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,11]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}