{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:01:20Z","timestamp":1773702080092,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T00:00:00Z","timestamp":1505779200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Fonden","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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00224-017-9806-5","type":"journal-article","created":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T01:49:55Z","timestamp":1505785795000},"page":"1443-1469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Weighted Online Problems with Advice"],"prefix":"10.1007","volume":"62","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3054-2997","authenticated-orcid":false,"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":[[2017,9,19]]},"reference":[{"key":"9806_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S., Hellwig, M.: Online Makespan Minimization with Parallel Schedules. In: SWAT, LNCS, vol. 8503, pp 13\u201325 (2014)","DOI":"10.1007\/978-3-319-08404-6_2"},{"key":"9806_CR2","doi-asserted-by":"publisher","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":"9806_CR3","doi-asserted-by":"crossref","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. In: ISAAC, LNCS, vol. 5878, pp 331\u2013340 (2009)","DOI":"10.1007\/978-3-642-10631-6_35"},{"issue":"2","key":"9806_CR4","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. J. Comput. Syst. Sci. 50(2), 244\u2013258 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9806_CR5","doi-asserted-by":"crossref","unstructured":"Boyar, J., Epstein, L., Favrholdt, L.M., Larsen, K.S., Levin, A.: Online Bounded Analysis. In: CSR, LNCS, vol. 9691, pp 131\u2013145 (2016)","DOI":"10.1007\/978-3-319-34171-2_10"},{"issue":"2","key":"9806_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/3056461","volume":"50","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv. (CSUR) 50(2), 19 (2017)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"9806_CR7","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: Advice Complexity for a Class of Online Problems. In: STACS, LIPIcs, vol. 30, pp. 116\u2013129 (2015). Full paper to appear in Theory of Computing Systems"},{"issue":"2","key":"9806_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/PL00009255","volume":"23","author":"M Chrobak","year":"1999","unstructured":"Chrobak, M., Noga, J.: LRU is better than FIFO. Algorithmica 23(2), 180\u2013185 (1999)","journal-title":"Algorithmica"},{"issue":"3","key":"9806_CR9","doi-asserted-by":"publisher","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."},{"key":"9806_CR10","unstructured":"D\u00fcrr, C., Konrad, C., Renault, M.P.: On the Power of Advice and Randomization for Online Bipartite Matching. In: ESA, LIPIcs, pp 37:1\u201337:16 (2016)"},{"issue":"24","key":"9806_CR11","doi-asserted-by":"publisher","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":"9806_CR12","doi-asserted-by":"publisher","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":"9806_CR13","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., Kudahl, C.: Advice Complexity of the Online Induced Subgraph Problem. In: MFCS, LIPIcs, vol. 58, pp 59:1\u201359:13 (2016)"},{"key":"9806_CR14","unstructured":"Mikkelsen, J.W.: Randomization can be as Helpful as a Glimpse of the Future in Online Computation. In: ICALP, LIPIcs, vol. 55, pp 39:1\u201339:14 (2016)"},{"key":"9806_CR15","doi-asserted-by":"publisher","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."},{"issue":"2","key":"9806_CR16","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"9806_CR17","volume-title":"Information Content of Online Problems: Advice Versus Determinism and Randomization","author":"J Smula","year":"2015","unstructured":"Smula, J.: Information Content of Online Problems: Advice Versus Determinism and Randomization. Ph.D. Thesis, ETH Z\u00fcrich (2015)"},{"key":"9806_CR18","volume-title":"Analysis of Hard Problems in Reoptimization and Online Computation","author":"A Sprock","year":"2013","unstructured":"Sprock, A.: Analysis of Hard Problems in Reoptimization and Online Computation. Ph.D. thesis, ETH Z\u00fcrich (2013)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9806-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9806-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9806-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,3]],"date-time":"2020-03-03T07:07:40Z","timestamp":1583219260000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9806-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,19]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["9806"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9806-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,19]]},"assertion":[{"value":"19 September 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}