{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:44:36Z","timestamp":1725857076449},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319341705"},{"type":"electronic","value":"9783319341712"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-34171-2_10","type":"book-chapter","created":{"date-parts":[[2016,5,30]],"date-time":"2016-05-30T06:34:18Z","timestamp":1464590058000},"page":"131-145","source":"Crossref","is-referenced-by-count":5,"title":["Online Bounded Analysis"],"prefix":"10.1007","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leah","family":"Epstein","sequence":"additional","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"}]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,31]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/PL00009158","volume":"18","author":"S Albers","year":"1997","unstructured":"Albers, S.: On the influence of lookahead in competitive paging algorithms. Algorithmica 18, 283\u2013305 (1997)","journal-title":"Algorithmica"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Albers, S., Favrholdt, L.M., Giel, O.: On paging with locality of reference. In: 34th Annual ACM Symposium on the Theory of Computing (STOC), pp. 258\u2013267 (2002)","DOI":"10.1145\/509907.509949"},{"key":"10_CR3","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: On the separation and equivalence of paging strategies. In: 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 229\u2013237 (2007)"},{"issue":"2","key":"10_CR4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-002-0965-6","volume":"34","author":"Y Azar","year":"2002","unstructured":"Azar, Y., Boyar, J., Epstein, L., Favrholdt, L.M., Larsen, K.S., Nielsen, M.N.: Fair versus unrestricted bin packing. Algorithmica 34(2), 181\u2013196 (2002)","journal-title":"Algorithmica"},{"issue":"2","key":"10_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1002\/(SICI)1099-1425(199808)1:2<67::AID-JOS6>3.0.CO;2-Y","volume":"1","author":"Y Azar","year":"1998","unstructured":"Azar, Y., Epstein, L.: On-line machine covering. J. Sched. 1(2), 67\u201377 (1998)","journal-title":"J. Sched."},{"issue":"1","key":"10_CR6","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(00)00258-9","volume":"268","author":"Y Azar","year":"2001","unstructured":"Azar, Y., Regev, O.: On-line bin-stretching. Theoret. Comput. Sci. 268(1), 17\u201341 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: 38th Annual ACM Symposium on the Theory of Computing (STOC), pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"issue":"1","key":"10_CR8","doi-asserted-by":"crossref","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 11(1), 73\u201391 (1994)","journal-title":"Algorithmica"},{"issue":"2","key":"10_CR9","doi-asserted-by":"crossref","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":"10_CR10","doi-asserted-by":"crossref","unstructured":"Boyar, J., Epstein, L., Favrholdt, L.M., Larsen, K.S., Levin, A.: Online bounded analysis. CoRR, abs\/1602.06708 (2016)","DOI":"10.1007\/978-3-319-34171-2_10"},{"key":"10_CR11","unstructured":"Boyar, J., Favrholdt, L., Mikkelsen, J., Kudahl, C.: Advice complexity for a class of online problems. In: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS). Leibniz International Proceedings in Informatics, vol. 30, pp. 116\u2013129 (2015)"},{"issue":"2","key":"10_CR12","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/1240233.1240245","volume":"3","author":"J Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. ACM Trans. Algorithms 3(2), 24 (2007). article 22","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"10_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00236-003-0124-9","volume":"40","author":"J Boyar","year":"2003","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S., Nielsen, M.N.: Extending the accommodating function. Acta Informatica 40(1), 3\u201335 (2003)","journal-title":"Acta Informatica"},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/PL00009286","volume":"25","author":"J Boyar","year":"1999","unstructured":"Boyar, J., Larsen, K.: The seat reservation problem. Algorithmica 25, 403\u2013417 (1999)","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR15","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1137\/S0097539799361786","volume":"31","author":"J Boyar","year":"2001","unstructured":"Boyar, J., Larsen, K.S., Nielsen, M.N.: The accommodating function\u2013a generalization of the competitive ratio. SIAM J. Comput. 31(1), 233\u2013258 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"10_CR16","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0304-3975(98)00118-2","volume":"209","author":"D Breslauer","year":"1998","unstructured":"Breslauer, D.: On competitive on-line paging with lookahead. Theoret. Comput. Sci. 209(1\u20132), 365\u2013375 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","first-page":"219","volume-title":"Automata, Languages and Programming","author":"S-H Chan","year":"2011","unstructured":"Chan, S.-H., Lam, T.-W., Lee, L.-K., Liu, C.-M., Ting, H.-F.: Sleep management on multiple machines for energy and flow time. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 219\u2013231. Springer, Heidelberg (2011)"},{"issue":"1","key":"10_CR18","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y Cho","year":"1980","unstructured":"Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM J. Comput. 9(1), 91\u2013103 (1980)","journal-title":"SIAM J. Comput."},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(88)90052-2","volume":"21","author":"J Csirik","year":"1988","unstructured":"Csirik, J., Totik, V.: On-line algorithms for a dual version of bin packing. Discrete Appl. Math. 21, 163\u2013167 (1988)","journal-title":"Discrete Appl. Math."},{"key":"10_CR20","doi-asserted-by":"crossref","first-page":"3694","DOI":"10.1016\/j.tcs.2009.04.023","volume":"410","author":"R Dorrigiv","year":"2009","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A., Munro, J.I.: On the relative dominance of paging algorithms. Theoret. Comput. Sci. 410, 3694\u20133701 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10_CR21","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s00453-012-9637-3","volume":"66","author":"MR Ehmsen","year":"2013","unstructured":"Ehmsen, M.R., Kohrt, J.S., Larsen, K.S.: List factoring and relative worst order analysis. Algorithmica 66(2), 287\u2013309 (2013)","journal-title":"Algorithmica"},{"issue":"2","key":"10_CR22","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.dam.2005.02.002","volume":"148","author":"L Epstein","year":"2005","unstructured":"Epstein, L.: Tight bounds for bandwidth allocation on two links. Discrete Appl. Math. 148(2), 181\u2013188 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"10_CR23","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s10878-006-9005-9","volume":"12","author":"L Epstein","year":"2006","unstructured":"Epstein, L., Favrholdt, L.M., Kohrt, J.S.: Separating online scheduling algorithms with the relative worst order ratio. J. Comb. Optim. 12(4), 363\u2013386 (2006)","journal-title":"J. Comb. Optim."},{"key":"10_CR24","unstructured":"Epstein, L., Noga, J., Seiden, S.S., Sgall, J., Woeginger, G.J.: Randomized online scheduling on two uniform machines. In: Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 317\u2013326 (1999)"},{"key":"10_CR25","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2014.09.011","volume":"562","author":"Y Giannakopoulos","year":"2015","unstructured":"Giannakopoulos, Y., Koutsoupias, E.: Competitive analysis of maintaining frequent items of a stream. Theoret. Comput. Sci. 562, 23\u201332 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR26","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"10_CR27","doi-asserted-by":"crossref","first-page":"79","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, 79\u2013119 (1988)","journal-title":"Algorithmica"},{"issue":"3","key":"10_CR28","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539794268042","volume":"30","author":"AR Karlin","year":"2000","unstructured":"Karlin, A.R., Phillips, S.J., Raghavan, P.: Markov paging. SIAM J. Comput. 30(3), 906\u2013922 (2000)","journal-title":"SIAM J. Comput."},{"key":"10_CR29","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 359\u2013364 (1996)"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. In: 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 394\u2013400 (1994)","DOI":"10.1109\/SFCS.1994.365677"},{"issue":"1","key":"10_CR31","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300\u2013317 (2000)","journal-title":"SIAM J. Comput."},{"key":"10_CR32","series-title":"IFIP Advances in Information and Communication Technology","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/978-3-642-15240-5_24","volume-title":"Theoretical Computer Science","author":"S Miyazaki","year":"2010","unstructured":"Miyazaki, S., Okamoto, K.: Improving the competitive ratios of the seat reservation problem. In: Calude, C.S., Sassone, V. (eds.) TCS 2010. IFIP AICT, vol. 323, pp. 328\u2013339. Springer, Heidelberg (2010)"},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Raghavan, P.: A statistical adversary for on-line algorithms. In: On-Line Algorithms. Series in Discrete Mathematics and Theoretical Computer Science, vol. 7, pp. 79\u201383. American Mathematical Society (1992)","DOI":"10.1090\/dimacs\/007\/05"},{"issue":"2","key":"10_CR34","doi-asserted-by":"crossref","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"},{"issue":"4","key":"10_CR35","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G.J.: A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20(4), 149\u2013154 (1997)","journal-title":"Oper. Res. Lett."},{"key":"10_CR36","unstructured":"Young, N.: Competitive paging and dual-guided algorithms for weighted caching and matching (thesis). Technical Report CS-TR-348-91, Computer Science Department, Princeton University (1991)"},{"key":"10_CR37","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"NE Young","year":"1994","unstructured":"Young, N.E.: The $$k$$ -server dual and loose competitiveness for paging. Algorithmica 11, 525\u2013541 (1994)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-34171-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T01:13:51Z","timestamp":1567991631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-34171-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319341705","9783319341712"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-34171-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}