{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T21:13:45Z","timestamp":1768252425991,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:00:00Z","timestamp":1592438400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:00:00Z","timestamp":1592438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100008394","name":"Natur og Univers, Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-1323-00247"],"award-info":[{"award-number":["DFF-1323-00247"]}],"id":[{"id":"10.13039\/100008394","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s00453-020-00728-0","type":"journal-article","created":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T08:02:41Z","timestamp":1592467361000},"page":"795-821","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Online Bin Covering with Advice"],"prefix":"10.1007","volume":"83","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":"Shahin","family":"Kamali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0560-3794","authenticated-orcid":false,"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,18]]},"reference":[{"issue":"8","key":"728_CR1","doi-asserted-by":"publisher","first-page":"2006","DOI":"10.1007\/s00224-018-9862-5","volume":"62","author":"S Angelopoulos","year":"2018","unstructured":"Angelopoulos, S., D\u00fcrr, C., Kamali, S., Renault, M.P., Ros\u00e9n, A.: Online bin packing with advice of small size. Theory Comput. Syst. 62(8), 2006\u20132034 (2018)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"728_CR2","first-page":"361","volume":"15","author":"EI \u00c1sgeirsson","year":"2002","unstructured":"\u00c1sgeirsson, E.I., Ayesta, U., Coffman, E.G., Jr., Etra, J., Momcilovic, P., Phillips, D.J., Vokhshoori, V., Wang, Z., Wolfe, J.: Closed on-line bin packing. Acta Cybernetica 15(3), 361\u2013367 (2002)","journal-title":"Acta Cybernetica"},{"issue":"4","key":"728_CR3","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/0196-6774(84)90004-X","volume":"5","author":"SF Assmann","year":"1984","unstructured":"Assmann, S.F., Johnson, D.S., Kleitman, D.J., Leung, J.Y.: On a dual version of the one-dimensional bin packing problem. J. Algorithms 5(4), 502\u2013525 (1984)","journal-title":"J. Algorithms"},{"key":"728_CR4","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. In: 26th Annual European Symposium on Algorithms (ESA), Leibniz International Proceedings in Informatics (LIPIcs), vol. 112, pp. 5:1\u20135:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"key":"728_CR5","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: A new lower bound for classic online bin packing. ArXiv 1807.05554 [cs:DS] (2018)"},{"key":"728_CR6","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H., Hromkovic, J., Komm, D.: A technique to obtain hardness results for randomized online algorithms\u2014a survey. In: Computing with New Resources\u2014Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, Lecture Notes in Computer Science, vol. 8808, pp. 264\u2013276. Springer (2014)","DOI":"10.1007\/978-3-319-13350-8_20"},{"key":"728_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"H B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H., 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. Computut. Sci. 554, 95\u2013108 (2014)","journal-title":"Theor. Computut. Sci."},{"key":"728_CR8","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.jcss.2017.01.001","volume":"86","author":"H B\u00f6ckenhauer","year":"2017","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovic, R., Kr\u00e1lovic, R.: On the advice complexity of the k-server problem. J. Comput. Syst. Sci. 86, 159\u2013170 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"728_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ic.2017.03.001","volume":"254","author":"H B\u00f6ckenhauer","year":"2017","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovic, R., Kr\u00e1lovic, R., M\u00f6mke, T.: Online algorithms with advice: the tape model. Inf. Comput. 254, 59\u201383 (2017)","journal-title":"Inf. Comput."},{"key":"728_CR10","unstructured":"Borodin, A., Pankratov, D., Salehi-Abari, A.: A simple PTAS for the dual bin packing problem and advice complexity of its online version. In: 1st Symposium on Simplicity in Algorithms (SOSA), LIPIcs, pp. 8:1\u20138:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"2","key":"728_CR11","doi-asserted-by":"publisher","first-page":"19:1","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. 50(2), 19:1\u201319:34 (2017)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"728_CR12","doi-asserted-by":"publisher","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(1), 507\u2013527 (2016)","journal-title":"Algorithmica"},{"issue":"2","key":"728_CR13","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(88)90052-2","volume":"21","author":"J Csirik","year":"1988","unstructured":"Csirik, J., Totik, V.: Online algorithms for a dual version of bin packing. Discrete Appl. Math. 21(2), 163\u2013167 (1988)","journal-title":"Discrete Appl. Math."},{"key":"728_CR14","unstructured":"D\u00fcrr, C., Konrad, C., Renault, M.P.: On the power of advice and randomization for online bipartite matching. In: 24th Annual European Symposium on Algorithms (ESA), LIPIcs, vol.\u00a057, pp. 37:1\u201337:16. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2016)"},{"key":"728_CR15","unstructured":"Grove, E.F.: Online bin packing with lookahead. In: 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 430\u2013436. SIAM (1995)"},{"key":"728_CR16","doi-asserted-by":"crossref","unstructured":"Hoberg, R., Rothvoss, T.: A logarithmic additive integrality gap for bin packing. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2616\u20132625. SIAM (2017)","DOI":"10.1137\/1.9781611974782.172"},{"key":"728_CR17","doi-asserted-by":"crossref","unstructured":"Hromkovic, J., Kr\u00e1lovic, R., Kr\u00e1lovic, R.: Information complexity of online problems. In: 35th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2010, Lecture Notes in Computer Science, vol. 6281, pp. 24\u201336. Springer (2010)","DOI":"10.1007\/978-3-642-15155-2_3"},{"issue":"1\u20133","key":"728_CR18","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/S0304-3975(03)00363-3","volume":"306","author":"K Jansen","year":"2003","unstructured":"Jansen, K., Solis-Oba, R.: An asymptotic fully polynomial time approximation scheme for bin covering. Theor. Comput. Sci. 306(1\u20133), 543\u2013551 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"728_CR19","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 312\u2013320. IEEE Computer Society (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"728_CR20","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42749-2","volume-title":"An Introduction to Online Computation-Determinism, Randomization, Advice","author":"D Komm","year":"2016","unstructured":"Komm, D.: An Introduction to Online Computation-Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2016)"},{"key":"728_CR21","unstructured":"Mikkelsen, J.W.: Randomization can be as helpful as a glimpse of the future in online computation. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 39:1\u201339:14. Springer (2016)"},{"issue":"4","key":"728_CR22","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1007\/s10100-016-0450-y","volume":"25","author":"MP Renault","year":"2017","unstructured":"Renault, M.P.: Online algorithms with advice for the dual bin packing problem. Central Eur. J. Oper. Res. 25(4), 953\u2013966 (2017)","journal-title":"Central Eur. J. Oper. Res."},{"key":"728_CR23","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."},{"key":"728_CR24","doi-asserted-by":"crossref","unstructured":"Rothvoss, T.: Approximating bin packing within o(log OPT * log log OPT) bins. In: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 20\u201329. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.11"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00728-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00728-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00728-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:35:12Z","timestamp":1623972912000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00728-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,18]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["728"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00728-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,18]]},"assertion":[{"value":"31 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}