{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:38:18Z","timestamp":1759667898828},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,4,13]],"date-time":"2011-04-13T00:00:00Z","timestamp":1302652800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Sci Res Dev"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00450-011-0149-1","type":"journal-article","created":{"date-parts":[[2011,4,12]],"date-time":"2011-04-12T21:48:19Z","timestamp":1302644899000},"page":"189-196","source":"Crossref","is-referenced-by-count":3,"title":["Probabilistic alternatives for competitive analysis"],"prefix":"10.1007","volume":"27","author":[{"given":"Benjamin","family":"Hiller","sequence":"first","affiliation":[]},{"given":"Tjark","family":"Vredeveld","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,4,13]]},"reference":[{"issue":"2","key":"149_CR1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.jcss.2004.08.002","volume":"70","author":"S Albers","year":"2005","unstructured":"Albers S, Favrholdt LM, Giel O (2005) On paging with locality of reference. J Comput Syst Sci 70(2):145\u2013175","journal-title":"J Comput Syst Sci"},{"key":"149_CR2","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1287\/moor.1040.0092","volume":"29","author":"EJ Anderson","year":"2004","unstructured":"Anderson EJ, Potts CN (2004) On-line scheduling of a single machine to minimize total weighted completion time. Math Oper Res 29:686\u2013697","journal-title":"Math Oper Res"},{"key":"149_CR3","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1137\/1.9781611973068.123","volume-title":"Proceedings of the 20th ACM-SIAM symposium on discrete algorithms","author":"S Angelopoulos","year":"2009","unstructured":"Angelopoulos S, Schweitzer P (2009) Paging and list update under bijective analysis. In: Proceedings of the 20th ACM-SIAM symposium on discrete algorithms, pp 1136\u20131145"},{"key":"149_CR4","first-page":"229","volume-title":"Proceedings of the 18th ACM-SIAM symposium on discrete algorithms","author":"S Angelopoulos","year":"2007","unstructured":"Angelopoulos S, Dorrigiv R, L\u00f3pez-Ortiz A (2007) On the separation and equivalence of paging strategies. In: Proceedings of the 18th ACM-SIAM symposium on discrete algorithms, pp 229\u2013237"},{"key":"149_CR5","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/978-3-540-45138-9_14","volume-title":"Proceedings of the 28th international symposium on mathematical foundations of computer science","author":"C Banderier","year":"2003","unstructured":"Banderier C, Beier R, Mehlhorn K (2003) Smoothed analysis of three combinatorial problems. In: Proceedings of the 28th international symposium on mathematical foundations of computer science. Lecture notes in computer science, vol 2747. Springer, Berlin, pp 198\u2013207"},{"key":"149_CR6","first-page":"98","volume-title":"Proceedings of the 12th European symp on algorithms (ESA)","author":"L Becchetti","year":"2004","unstructured":"Becchetti L (2004) Modeling locality: a probabilistic analysis of LRU and FWF. In: Proceedings of the 12th European symp on algorithms (ESA), pp 98\u2013109"},{"key":"149_CR7","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/1008731.1008732","volume":"51","author":"L Becchetti","year":"2004","unstructured":"Becchetti L, Leonardi S (2004) Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J ACM 51:517\u2013539","journal-title":"J ACM"},{"issue":"1","key":"149_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1287\/moor.1050.0170","volume":"31","author":"L Becchetti","year":"2006","unstructured":"Becchetti L, Leonardi S, Marchetti-Spaccamela A, Sch\u00e4fer G, Vredeveld T (2006) Average case and smoothed competitive analysis for the multi-level feedback algorithm. Math Oper Res 31(1):85\u2013108","journal-title":"Math Oper Res"},{"key":"149_CR9","first-page":"739","volume-title":"Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms","author":"R Beier","year":"2004","unstructured":"Beier R, Czumaj A, Krysta P, V\u00f6cking B (2004) Computing equilibria for congestion games with (im)perfect information. In: Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms, pp 739\u2013748"},{"key":"149_CR10","first-page":"279","volume-title":"Proceedings of the 16th annual ACM symposium on theory of computing","author":"JL Bentley","year":"1984","unstructured":"Bentley JL, Johnson DS, Leighton FT, McGeoch CC, McGeoch LA (1984) Some unexpected expected behavior results for bin packing. In: Proceedings of the 16th annual ACM symposium on theory of computing, pp 279\u2013288"},{"issue":"2","key":"149_CR11","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 (1995) Competitive paging with locality of reference. J Comput Syst Sci 50(2):244\u2013258","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"149_CR12","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A Borodin","year":"1992","unstructured":"Borodin A, Linial N, Saks ME (1992) An optimal on-line algorithm for metrical task systems. J ACM 39(4):745\u2013763","journal-title":"J ACM"},{"issue":"1","key":"149_CR13","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0020-0190(92)90023-O","volume":"43","author":"B Chandra","year":"1992","unstructured":"Chandra B (1992) Does randomization help in on-line bin packing? Inf Process Lett 43(1):15\u201319","journal-title":"Inf Process Lett"},{"issue":"3","key":"149_CR14","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1287\/opre.33.3.548","volume":"33","author":"EG Coffman Jr","year":"1985","unstructured":"Coffman EG Jr, Gilbert EN (1985) On the expected relative performance of list scheduling. Oper Res 33(3):548\u2013561","journal-title":"Oper Res"},{"key":"149_CR15","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0019-9958(80)90050-9","volume":"44","author":"EG Coffman Jr","year":"1980","unstructured":"Coffman EG Jr, So K, Hofri M, Yao AC (1980) A stochastic model of bin-packing. Inf Control 44:105\u2013115","journal-title":"Inf Control"},{"key":"149_CR16","volume-title":"Approximation algorithms for NP-hard problems","author":"EG Coffman Jr","year":"1997","unstructured":"Coffman EG Jr, Garey MR, Johnson DS, (1997) Approximation algorithms for bin packing: a survey. In: Hochbaum DS (ed) Approximation algorithms for NP-hard problems. PWS, Boston"},{"issue":"1","key":"149_CR17","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/S0036144501395423","volume":"44","author":"EG Coffman Jr","year":"2002","unstructured":"Coffman EG Jr, Courcoubetis C, Garey MR, Johnson DS, Shor PW, Weber RR, Yannakakis M (2002) Perfect packing theorems and the average-case behavior of optimal and online bin packing. SIAM Rev 44(1):95\u2013108","journal-title":"SIAM Rev"},{"issue":"1","key":"149_CR18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10107-007-0204-7","volume":"119","author":"J Correa","year":"2009","unstructured":"Correa J, Wagner M (2009) LP-based online scheduling: from single machine to parallel machines. Math Program 119(1):109\u2013136","journal-title":"Math Program"},{"key":"149_CR19","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00453-001-0041-7","volume":"11","author":"J Csirik","year":"2001","unstructured":"Csirik J, Johnson DS (2001) Bounded space on-line bin packing: best is better than first. Algorithmica 11:115\u2013138","journal-title":"Algorithmica"},{"key":"149_CR20","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A Fiat","year":"1991","unstructured":"Fiat A, Karp RM, Luby M, McGeoch LA, Sleator DD, Young NE (1991) Competitive paging algorithms. J Algorithms 12:685\u2013699","journal-title":"J Algorithms"},{"issue":"1","key":"149_CR21","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321796.321800","volume":"21","author":"PA Franaszek","year":"1974","unstructured":"Franaszek PA, Wagner TJ (1974) Some distribution-free aspects of paging algorithm performance. J ACM 21(1):31\u201339","journal-title":"J ACM"},{"key":"149_CR22","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 RL (1966) Bounds for certain multiprocessor anomalies. Bell Syst Tech J 45:1563\u20131581","journal-title":"Bell Syst Tech J"},{"key":"149_CR23","unstructured":"Hiller B (2009) Online optimization: probabilistic analysis and algorithm engineering. PhD thesis, TU Berlin"},{"key":"149_CR24","unstructured":"Hiller B, Vredeveld T (2008) On the optimality of least recently used. ZIB-Report 08-39, Zuse Institute Berlin"},{"key":"149_CR25","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1007\/978-3-540-87744-8_44","volume-title":"Proceedings of the 16th annual European symposium on algorithms","author":"B Hiller","year":"2008","unstructured":"Hiller B, Vredeveld T (2008) Probabilistic analysis of online bin coloring algorithms via stochastic comparison. In: Proceedings of the 16th annual European symposium on algorithms. Lecture notes in computer science, vol 5193. Springer, Berlin, pp 528\u2013539"},{"key":"149_CR26","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/3-540-61310-2_30","volume-title":"Proceedings of the 5th conference on integer programming and combinatorial optimization IPCO","author":"H Hoogeveen","year":"1996","unstructured":"Hoogeveen H, Vestjens APA (1996) Optimal on-line algorithms for single-machine scheduling. In: Cunningham WH, McCormick ST, Queyranne M (eds) Proceedings of the 5th conference on integer programming and combinatorial optimization IPCO. Lecture notes in computer science, vol 1084. Springer, Berlin, pp 404\u2013414"},{"issue":"8","key":"149_CR27","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Fast algorithms for bin packing. J Comput Syst Sci 8(8):272\u2013314","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"149_CR28","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson DS, Demers A, Ullman JD, Garey MR, Graham RL (1974) Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J Comput 3(4):299\u2013325","journal-title":"SIAM J Comput"},{"issue":"4","key":"149_CR29","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. J ACM 47(4):617\u2013643","journal-title":"J ACM"},{"key":"149_CR30","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin AR, Manasse MS, Rudolph L, Sleator DD (1988) Competitive snoopy caching. Algorithmica 3:70\u2013119","journal-title":"Algorithmica"},{"issue":"2","key":"149_CR31","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539794268042","volume":"30","author":"AR Karlin","year":"2000","unstructured":"Karlin AR, Phillips SJ, Raghavan P (2000) Markov paging. SIAM J Comput 30(2):906\u2013922","journal-title":"SIAM J Comput"},{"key":"149_CR32","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T Kawaguchi","year":"1986","unstructured":"Kawaguchi T, Kyan S (1986) Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J Comput 15:1119\u20131129","journal-title":"SIAM J Comput"},{"key":"149_CR33","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1109\/SFCS.1994.365677","volume-title":"Proceedings of the 35th annual IEEE symposium on foundations of computer science","author":"E Koutsoupias","year":"1994","unstructured":"Koutsoupias E, Papadimitriou C (1994) Beyond competitive analysis. In: Proceedings of the 35th annual IEEE symposium on foundations of computer science, pp 394\u2013400"},{"key":"149_CR34","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/3-540-44676-1_6","volume-title":"Proceedings of the 9th annual European symposium on algorithms","author":"SO Krumke","year":"2001","unstructured":"Krumke SO, de Paepe WE, Stougie L, Rambau J (2001) Online bin coloring. In: auf der Heide FM (ed) Proceedings of the 9th annual European symposium on algorithms. Lecture notes in computer science, vol 2161, pp 74\u201384"},{"issue":"3","key":"149_CR35","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee CC, Lee DT (1985) A simple online bin-packing algorithm. J\u00a0ACM 32(3):562\u2013572","journal-title":"J\u00a0ACM"},{"key":"149_CR36","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"LA McGeoch","year":"1991","unstructured":"McGeoch LA, Sleator DD (1991) A strongly competitive randomized paging algorithm. Algorithmica 6:816\u2013825","journal-title":"Algorithmica"},{"key":"149_CR37","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"RH M\u00f6hring","year":"1999","unstructured":"M\u00f6hring RH, Schulz AS, Uetz M (1999) Approximation in stochastic scheduling: the power of LP-based priority policies. J ACM 46:924\u2013942","journal-title":"J ACM"},{"key":"149_CR38","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","volume":"130","author":"R Motwani","year":"1994","unstructured":"Motwani R, Phillips S, Torng E (1994) Non-clairvoyant scheduling. Theor Comput Sci 130:17\u201347","journal-title":"Theor Comput Sci"},{"key":"149_CR39","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1145\/1132516.1132587","volume-title":"STOC \u201906: Proceedings of the 38th annual ACM symposium on theory of computing","author":"K Panagiotou","year":"2006","unstructured":"Panagiotou K, Souza A (2006) On adequate performance measures for paging. In: STOC \u201906: Proceedings of the 38th annual ACM symposium on theory of computing, pp 487\u2013496"},{"key":"149_CR40","volume-title":"Handbook of scheduling: algorithms, models, and performance analysis","author":"K Pruhs","year":"2004","unstructured":"Pruhs K, Sgall J, Torng E (2004) Online scheduling. In: Leung J (ed) Handbook of scheduling: algorithms, models, and performance analysis. CRC Press, Boca Raton"},{"issue":"1\u20133","key":"149_CR41","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(91)90087-D","volume":"34","author":"MB Richey","year":"1991","unstructured":"Richey MB (1991) Improved bounds for harmonic-based bin packing algorithms. Discrete Appl Math 34(1\u20133):203\u2013227","journal-title":"Discrete Appl Math"},{"key":"149_CR42","doi-asserted-by":"crossref","unstructured":"Scharbrodt M, Schickinger T, Steger A (2006) A new average case analysis for completion time scheduling. J. ACM 121\u2013146","DOI":"10.1145\/1120582.1120585"},{"key":"149_CR43","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1287\/opre.16.3.687","volume":"16","author":"L Schrage","year":"1968","unstructured":"Schrage L (1968) A proof of the optimality of the shortest remaining processing time discipline. Oper Res 16:687\u2013690","journal-title":"Oper Res"},{"key":"149_CR44","first-page":"592","volume-title":"Proceedings of the 32nd ACM symposium on theory of computing","author":"S Seiden","year":"2000","unstructured":"Seiden S (2000) A guessing game and randomized online algorithms. In: Proceedings of the 32nd ACM symposium on theory of computing, pp 592\u2013601"},{"issue":"2","key":"149_CR45","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02579171","volume":"6","author":"PW Shor","year":"1986","unstructured":"Shor PW (1986) The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6(2):179\u2013200","journal-title":"Combinatorica"},{"issue":"2","key":"149_CR46","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202\u2013208","journal-title":"Commun ACM"},{"key":"149_CR47","doi-asserted-by":"crossref","unstructured":"Souza A (2010) Adversarial models in paging\u2014bridging the gap between theory and practice. Comput Sci Res Dev, this issue","DOI":"10.1007\/s00450-011-0152-6"},{"key":"149_CR48","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00224-005-1261-z","volume":"39","author":"A Souza","year":"2006","unstructured":"Souza A, Steger A (2006) The expected competitive ratio for weighted completion time scheduling. Theory Comput Syst 39:121\u2013136","journal-title":"Theory Comput Syst"},{"key":"149_CR49","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman DA, Teng SH (2004) Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J ACM 51:385\u2013463","journal-title":"J ACM"},{"issue":"1","key":"149_CR50","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/PL00009192","volume":"20","author":"E Torng","year":"1998","unstructured":"Torng E (1998) A unified analysis of paging and caching. Algorithmica 20(1):175\u2013200","journal-title":"Algorithmica"},{"issue":"1","key":"149_CR51","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1006\/jagm.1996.0005","volume":"20","author":"A Vliet van","year":"1996","unstructured":"van Vliet A (1996) On the asymptotic worst case behavior of harmonic fit. J Algorithms 20(1):113\u2013136","journal-title":"J Algorithms"},{"key":"149_CR52","unstructured":"Vestjens APA (1997) On-line machine scheduling. PhD thesis, Eindhoven University of Technology, Netherlands"},{"key":"149_CR53","doi-asserted-by":"crossref","unstructured":"Vredeveld T (2010) Stochastic online scheduling. Comput Sci Res Dev, this issue","DOI":"10.1007\/s00450-011-0153-5"},{"issue":"2","key":"149_CR54","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/322186.322187","volume":"27","author":"AC Yao","year":"1980","unstructured":"Yao AC (1980) New algorithms for bin packing. J ACM 27(2):207\u2013227","journal-title":"J ACM"},{"issue":"6","key":"149_CR55","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"NE Young","year":"1994","unstructured":"Young NE (1994) The k-server dual and loose competitiveness for paging. Algorithmica 11(6):525\u2013541","journal-title":"Algorithmica"},{"issue":"1","key":"149_CR56","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"NE Young","year":"2000","unstructured":"Young NE (2000) On-line paging against adversarially biased random inputs. J Algorithms 37(1):218\u2013235","journal-title":"J Algorithms"}],"container-title":["Computer Science - Research and Development"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00450-011-0149-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00450-011-0149-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00450-011-0149-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:06:40Z","timestamp":1560125200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00450-011-0149-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,13]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["149"],"URL":"https:\/\/doi.org\/10.1007\/s00450-011-0149-1","relation":{},"ISSN":["1865-2034","1865-2042"],"issn-type":[{"value":"1865-2034","type":"print"},{"value":"1865-2042","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,13]]}}}