{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:29:01Z","timestamp":1742912941245,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319037790"},{"type":"electronic","value":"9783319037806"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03780-6_20","type":"book-chapter","created":{"date-parts":[[2013,11,21]],"date-time":"2013-11-21T01:13:18Z","timestamp":1384996398000},"page":"226-237","source":"Crossref","is-referenced-by-count":1,"title":["Online Bin Covering: Expectations vs. Guarantees"],"prefix":"10.1007","author":[{"given":"Marie G.","family":"Christ","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"20_CR1","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/0196-6774(84)90004-X","volume":"5","author":"S.F. Assmann","year":"1984","unstructured":"Assmann, S.F., Johnson, D.S., Kleitman, D.J., Leung, J.Y.-T.: On a dual version of the one-dimensional bin packing problem. J. Algorithms\u00a05(4), 502\u2013525 (1984)","journal-title":"J. Algorithms"},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S. Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica\u00a011(1), 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. ACM Trans. Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240245"},{"issue":"5","key":"20_CR4","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.jcss.2007.03.001","volume":"73","author":"J. Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst order ratio applied to paging. J. Comput. Sys. Sci.\u00a073(5), 818\u2013843 (2007)","journal-title":"J. Comput. Sys. Sci."},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-31155-0_29","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"J. Boyar","year":"2012","unstructured":"Boyar, J., Gupta, S., Larsen, K.S.: Access graphs results for LRU versus FIFO under relative worst order analysis. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 328\u2013339. Springer, Heidelberg (2012)"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-40104-6_17","volume-title":"Algorithms and Data Structures","author":"J. Boyar","year":"2013","unstructured":"Boyar, J., Gupta, S., Larsen, K.S.: Relative interval analysis of paging algorithms on access graphs. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 195\u2013206. Springer, Heidelberg (2013)"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-03367-4_11","volume-title":"Algorithms and Data Structures","author":"J. Boyar","year":"2009","unstructured":"Boyar, J., Irani, S., Larsen, K.S.: A comparison of performance measures for online algorithms. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 119\u2013130. Springer, Heidelberg (2009)"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-642-29700-7_28","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"J. Boyar","year":"2012","unstructured":"Boyar, J., Larsen, K.S., Maiti, A.: A comparison of performance measures via online search. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol.\u00a07285, pp. 303\u2013314. Springer, Heidelberg (2012)"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Christ, M., Favrholdt, L.M., Larsen, K.S.: Online bin covering: Expectations vs. guarantees. arXiv:1309.6477(cs.DS) (2013)","DOI":"10.1007\/978-3-319-03780-6_20"},{"issue":"2","key":"20_CR10","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0196-6774(91)90001-F","volume":"12","author":"J. Csirik","year":"1991","unstructured":"Csirik, J., Frenk, J.B.G., Galambos, G., Kan, A.H.G.R.: Probabilistic analysis of algorithms for dual bin packing problems. J. Algorithms\u00a012(2), 189\u2013203 (1991)","journal-title":"J. Algorithms"},{"issue":"2","key":"20_CR11","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.\u00a021(2), 163\u2013167 (1988)","journal-title":"Discrete Appl. Math."},{"key":"20_CR12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BFb0029568","volume-title":"Online Algorithms 1996","author":"J. Csirik","year":"1998","unstructured":"Csirik, J., Woeginger, G.: On-line packing and covering problems. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol.\u00a01442, pp. 147\u2013177. Springer, Heidelberg (1998)"},{"issue":"3","key":"20_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/1086649.1086670","volume":"36","author":"R. Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News\u00a036(3), 67\u201381 (2005)","journal-title":"SIGACT News"},{"key":"20_CR14","unstructured":"Durrett, R.: Probability: Theory and Examples. Dixbury Press (1991)"},{"issue":"2","key":"20_CR15","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-012-9637-3","volume":"66","author":"M.R. Ehmsen","year":"2013","unstructured":"Ehmsen, M.R., Kohrt, J.S., Larsen, K.S.: List factoring and relative worst order analysis. Algorithmica\u00a066(2), 287\u2013309 (2013)","journal-title":"Algorithmica"},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s10951-009-0129-5","volume":"15","author":"L. Epstein","year":"2012","unstructured":"Epstein, L., Favrholdt, L.M., Kohrt, J.S.: Comparing online algorithms for bin packing problems. J. Scheduling\u00a015(1), 13\u201321 (2012)","journal-title":"J. Scheduling"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Hoffmann-J\u00f8rgensen, J.: Probability with a View towards Statistics, vol.\u00a0I. Chapman\u00a0&\u00a0Hall (1994)","DOI":"10.1007\/978-1-4899-3019-4"},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"2810","DOI":"10.1016\/j.dam.2007.11.004","volume":"156","author":"E.G. Coffman Jr.","year":"2008","unstructured":"Coffman Jr., E.G., Csirik, J., R\u00f3nyai, L., Zsb\u00e1n, A.: Random-order bin packing. Discrete Appl. Math.\u00a0156, 2810\u20132816 (2008)","journal-title":"Discrete Appl. Math."},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A.R. Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica\u00a03, 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"20_CR20","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: SODA, pp. 359\u2013364 (1996)"},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"C.C. Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line bin-packing algorithm. J. ACM\u00a032(3), 562\u2013572 (1985)","journal-title":"J. ACM"},{"issue":"3","key":"20_CR22","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"P.V. Ramanan","year":"1989","unstructured":"Ramanan, P.V., Brown, D.J., Lee, C.C., Lee, D.T.: On-line bin packing in linear time. J. Algorithms\u00a010(3), 305\u2013326 (1989)","journal-title":"J. Algorithms"},{"issue":"5","key":"20_CR23","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"S.S. Seiden","year":"2002","unstructured":"Seiden, S.S.: On the online bin packing problem. J. ACM\u00a049(5), 640\u2013671 (2002)","journal-title":"J. ACM"},{"issue":"2","key":"20_CR24","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Comm. ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Comm. ACM"},{"issue":"4","key":"20_CR25","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1137\/0406045","volume":"6","author":"G. Woeginger","year":"1993","unstructured":"Woeginger, G.: Improved space for bounded space, on-line bin-packing. SIAM J. Disc. Math.\u00a06(4), 575\u2013581 (1993)","journal-title":"SIAM J. Disc. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03780-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T08:40:04Z","timestamp":1558687204000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03780-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319037790","9783319037806"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03780-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}