{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T06:53:58Z","timestamp":1773471238190,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,8,1]],"date-time":"2016-08-01T00:00:00Z","timestamp":1470009600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Fonden (DK)","doi-asserted-by":"publisher","award":["VKR023219"],"award-info":[{"award-number":["VKR023219"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d (DK)","doi-asserted-by":"publisher","award":["DFF \u2013 1323-00247"],"award-info":[{"award-number":["DFF \u2013 1323-00247"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00224-016-9688-y","type":"journal-article","created":{"date-parts":[[2016,8,1]],"date-time":"2016-08-01T02:08:12Z","timestamp":1470017292000},"page":"1128-1177","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The Advice Complexity of a Class of Hard Online Problems"],"prefix":"10.1007","volume":"61","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"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":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper W.","family":"Mikkelsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,1]]},"reference":[{"issue":"2","key":"9688_CR1","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput. 39 (2), 361\u2013370 (2009).","journal-title":"SIAM J. Comput."},{"key":"9688_CR2","doi-asserted-by":"crossref","unstructured":"Barhum, K.: Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem. Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Lecture Notes in Computer Science. Springer, 77\u201388 (2014).","DOI":"10.1007\/978-3-319-04298-5_8"},{"key":"9688_CR3","unstructured":"Barhum, K., B\u00f6ckenhauer, H.J., Fori\u0161ek, M., Gebauer, H., Hromkovi\u010d, J., Krug, S., Smula, J., Steffen, B.: On the Power of Advice and Randomization for the Disjoint Path Allocation Problem. In Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Lecture Notes in Computer Science. Springer, 89\u2013101 (2014)."},{"issue":"1","key":"9688_CR4","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/s00453-013-9819-7","volume":"70","author":"MP Bianchi","year":"2014","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica. 70 (1), 92\u2013111 (2014).","journal-title":"Algorithmica"},{"key":"9688_CR5","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"HJ B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci. 554, 95\u2013108 (2014).","journal-title":"Theor. Comput. Sci."},{"key":"9688_CR6","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the Advice Complexity of the K-Server Problem. Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science. Springer, 207\u2013218 (2011)."},{"key":"9688_CR7","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the Advice Complexity of Online Problems. Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science. Springer, 331\u2013340 (2009)."},{"key":"9688_CR8","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"HJ B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: The online knapsack problem: Advice and randomization. Theor. Comput. Sci. 554, 95\u2013108 (2014).","journal-title":"Theor. Comput. Sci."},{"key":"9688_CR9","doi-asserted-by":"crossref","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: On the List Update Problem with Advice. Proceedings of the 8th International Conference on Language and Automata Theory and Applications (LATA), Lecture Notes in Computer Science. Springer, 210\u2013221 (2014). Full paper to appear in Information and Computation.","DOI":"10.1007\/978-3-319-04921-2_17"},{"key":"9688_CR10","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s00453-014-9955-8","volume":"74","author":"J Boyar","year":"2016","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: Online bin packing with advice. Algorithmica. 74, 507\u2013527 (2016).","journal-title":"Algorithmica"},{"issue":"1-3","key":"9688_CR11","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.tcs.2004.08.015","volume":"332","author":"M Demange","year":"2005","unstructured":"Demange, M., Paschos, V.T.: On-line vertex-covering. Theor. Comput. Sci. 332 (1-3), 83\u2013108 (2005).","journal-title":"Theor. Comput. Sci."},{"key":"9688_CR12","unstructured":"Dinitz, J.H., Stinson, D.R., (Eds): Contemporary Design Theory: a Collection of Surveys. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1992)."},{"issue":"1","key":"9688_CR13","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s00224-014-9592-2","volume":"56","author":"S Dobrev","year":"2015","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Advice complexity of maximum independent set in sparse and bipartite graphs. Theory. Comput. Syst. 56 (1), 197\u2013219 (2015).","journal-title":"Theory. Comput. Syst."},{"issue":"3","key":"9688_CR14","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1051\/ita\/2009012","volume":"43","author":"S Dobrev","year":"2009","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: Measuring the problem-relevant information in input. RAIRO - Theor. Inf. Appl. 43 (3), 585\u2013613 (2009).","journal-title":"RAIRO - Theor. Inf. Appl."},{"issue":"24","key":"9688_CR15","doi-asserted-by":"crossref","first-page":"2642","DOI":"10.1016\/j.tcs.2010.08.007","volume":"412","author":"Y Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. Theor. Comput. Sci. 412 (24), 2642\u20132656 (2011).","journal-title":"Theor. Comput. Sci."},{"key":"9688_CR16","unstructured":"Erdo\u030bs, P., Spencer, J.: Probabilistic Methods in Combinatorics. Academic Press, 1974."},{"key":"9688_CR17","unstructured":"Fori\u0161ek, M., Keller, L., Steinov\u00e1, M.: Advice Complexity of Online Coloring for Paths. In Proceedings of the 6th International Conference on Language and Automata Theory and Applications (LATA), Lecture Notes in Computer Science. Springer, 228\u2013239 (2012)."},{"key":"9688_CR18","unstructured":"Gupta, S., Kamali, S., L\u00f3pez-Ortiz, A.: On Advice Complexity of the K-Server Problem under Sparse Metrics. Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science. Springer, 55\u201367 (2013)."},{"issue":"2","key":"9688_CR19","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1016\/S0304-3975(01)00411-X","volume":"289","author":"MM Halld\u00f3rsson","year":"2002","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Taketomi, S.: Online independent sets. Theor. Comput. Sci. 289 (2), 953\u2013962 (2002).","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9688_CR20","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(94)90157-0","volume":"130","author":"MM Halld\u00f3rsson","year":"1994","unstructured":"Halld\u00f3rsson, M.M., Szegedy, M.: Lower bounds for on-line graph coloring. Theor. Comput. Sci. 130 (1), 163\u2013174 (1994).","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9688_CR21","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2212\ud835\udf16 . Acta Math. 182 (1), 105\u2013142 (1999).","journal-title":"Acta Math."},{"key":"9688_CR22","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information Complexity of Online Problems. In Proceedings of the 35th Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science. Springer, 24\u201336 (2010)."},{"key":"9688_CR23","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica. 3, 77\u2013119 (1988).","journal-title":"Algorithmica"},{"key":"9688_CR24","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the Advice Complexity of the Set Cover Problem. In Proceedings of the 7th International Computer Science Symposium in Russia (CSR), Lecture Notes in Computer Science. Springer, 241\u2013252 (2012)."},{"key":"9688_CR25","first-page":"73","volume":"68","author":"A Marchetti-Spaccamela","year":"1995","unstructured":"Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68, 73\u2013104 (1995).","journal-title":"Math. Program."},{"key":"9688_CR26","doi-asserted-by":"crossref","unstructured":"Mikkelsen, J.W.: Optimal Online Edge Coloring of Planar Graphs with Advice. Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science. Springer, 352\u2013364 (2015).","DOI":"10.1007\/978-3-319-18173-8_26"},{"key":"9688_CR27","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005).","DOI":"10.1017\/CBO9780511813603"},{"issue":"12","key":"9688_CR28","doi-asserted-by":"crossref","first-page":"714","DOI":"10.1016\/j.ipl.2014.06.013","volume":"114","author":"S Miyazaki","year":"2014","unstructured":"Miyazaki, S.: On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett. 114 (12), 714\u2013717 (2014).","journal-title":"Inf. Process. Lett."},{"key":"9688_CR29","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. Proceedings of the 29th Symposium on Theory of Computing (STOC). ACM, 475\u2013484 (1997).","DOI":"10.1145\/258533.258641"},{"key":"9688_CR30","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.tcs.2015.07.050","volume":"600","author":"MP Renault","year":"2015","unstructured":"Renault, M.P., Ros\u00e9n, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. Theor. Comput. Sci. 600, 155\u2013170 (2015).","journal-title":"Theor. Comput. Sci."},{"key":"9688_CR31","doi-asserted-by":"crossref","unstructured":"Seibert, S., Sprock, A., Unger, W.: Advice Complexity of the Online Coloring Problem. In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science. Springer, 345\u2013357 (2013).","DOI":"10.1007\/978-3-642-38233-8_29"},{"key":"9688_CR32","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM. 28 (2), 202\u2013208 (1985).","DOI":"10.1145\/2786.2793"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9688-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9688-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9688-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9688-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T20:22:25Z","timestamp":1568233345000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9688-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,1]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["9688"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9688-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,1]]}}}