{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:14Z","timestamp":1750307594140,"version":"3.41.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,1,25]],"date-time":"2010-01-25T00:00:00Z","timestamp":1264377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2010,1,25]]},"abstract":"<jats:p>Pros and cons of competitive analysis have been debated since its inception in mid 1980s. Much of this discussion centered around the accuracy of performance evaluation methods for paging, which is probably the most central among online optimization problems studied in the literature, and, at the same time, ironically, the most prominent example of shortcomings of competitive analysis. In this quarter's column, Reza Dorrigiv and Alejandro Lopez-Ortiz review the history of the problem, discuss several performance models from the literature, and propose a new model that avoids shortcomings of previous approaches.<\/jats:p>\n          <jats:p>If you are interested in contributing to the column as a guest writer, feel free to contact me by email. All kinds of contributions related to online algorithms and competitive analysis are of interest: technical articles, surveys, conference reports, opinion pieces, and other.<\/jats:p>","DOI":"10.1145\/1711475.1711499","type":"journal-article","created":{"date-parts":[[2010,1,26]],"date-time":"2010-01-26T14:01:38Z","timestamp":1264514498000},"page":"98","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Introduction to the SIGACT news online algorithms column"],"prefix":"10.1145","volume":"40","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,25]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"229","volume-title":"Proc. SODA","author":"Angelopoulos S.","year":"2007","unstructured":"{ADLO07} S. Angelopoulos , R. Dorrigiv , and A. L\u00f3pez-Ortiz . On the separation and equivalence of paging strategies . In Proc. SODA , pages 229 - 237 , 2007 . {ADLO07} S. Angelopoulos, R. Dorrigiv, and A. L\u00f3pez-Ortiz. On the separation and equivalence of paging strategies. In Proc. SODA, pages 229-237, 2007."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792918.1792953"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_9"},{"key":"e_1_2_1_5_1","volume-title":"AAAI","author":"Angelopoulos Spyros","year":"2008","unstructured":"{ALOH08} Spyros Angelopoulos , Alejandro L\u00f3pez-Ortiz , and Ang\u00e8le M. Hamel . Optimal scheduling of contract algorithms with soft deadlines . In AAAI , 2008 . {ALOH08} Spyros Angelopoulos, Alejandro L\u00f3pez-Ortiz, and Ang\u00e8le M. Hamel. Optimal scheduling of contract algorithms with soft deadlines. In AAAI, 2008."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496893"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_8_1","volume-title":"Empirical model-building and response surface","author":"Box G. E. P.","year":"1986","unstructured":"{BD86} G. E. P. Box and N. R Draper . Empirical model-building and response surface . John Wiley & Sons, Inc. , 1986 . {BD86} G. E. P. Box and N. R Draper. Empirical model-building and response surface. John Wiley & Sons, Inc., 1986."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294264"},{"key":"e_1_2_1_10_1","first-page":"98","volume-title":"Proc. ESA","author":"Becchetti L.","year":"2004","unstructured":"{Bec04} L. Becchetti . Modeling locality : A probabilistic analysis of LRU and FWF . In Proc. ESA , pages 98 - 109 , 2004 . {Bec04} L. Becchetti. Modeling locality: A probabilistic analysis of LRU and FWF. In Proc. ESA, pages 98-109, 2004."},{"key":"e_1_2_1_11_1","first-page":"53","volume-title":"Proc. SODA","author":"Bachrach R.","year":"1997","unstructured":"{BEY97} R. Bachrach and R. El-Yaniv . Online list accessing algorithms and their applications: Recent empirical evidence . In Proc. SODA , pages 53 - 62 , 1997 . {BEY97} R. Bachrach and R. El-Yaniv. Online list accessing algorithms and their applications: Recent empirical evidence. In Proc. SODA, pages 53-62, 1997."},{"key":"e_1_2_1_12_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998","unstructured":"{BEY98} A. Borodin and R. El-Yaniv . Online Computation and Competitive Analysis . Cambridge University Press , 1998 . {BEY98} A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1757536.1757552"},{"key":"e_1_2_1_14_1","first-page":"718","volume-title":"Proc. SODA","author":"Boyar J.","year":"2005","unstructured":"{BFL05} J. Boyar , L. M. Favrholdt , and K. S. Larsen . The relative worst order ratio applied to paging . In Proc. SODA , pages 718 - 727 , 2005 . {BFL05} J. Boyar, L. M. Favrholdt, and K. S. Larsen. The relative worst order ratio applied to paging. In Proc. SODA, pages 718-727, 2005."},{"key":"e_1_2_1_15_1","first-page":"137","volume-title":"CCCG","author":"Biedl Therese C.","year":"2002","unstructured":"{BHH+02} Therese C. Biedl , Masud Hasan , Joseph Douglas Horton , Alejandro L\u00f3pez-Ortiz , and Tom\u00e1s Vinar . Searching for the center of a circle . In CCCG , pages 137 - 141 , 2002 . {BHH+02} Therese C. Biedl, Masud Hasan, Joseph Douglas Horton, Alejandro L\u00f3pez-Ortiz, and Tom\u00e1s Vinar. Searching for the center of a circle. In CCCG, pages 137-141, 2002."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1021"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009286"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361786"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009255"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12450-1_10"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1980.230464"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1070838.1070856"},{"key":"e_1_2_1_25_1","first-page":"32","volume-title":"Proc. 6th ISAAC","author":"Datta A.","year":"1995","unstructured":"{DHS95} A. Datta , Ch. Hipke , and S. Schuierer . Competitive searching in polygons--beyond generalized streets . In Proc. 6th ISAAC , pages 32 - 41 . LNCS 1004, 1995 . {DHS95} A. Datta, Ch. Hipke, and S. Schuierer. Competitive searching in polygons--beyond generalized streets. In Proc. 6th ISAAC, pages 32-41. LNCS 1004, 1995."},{"issue":"3","key":"e_1_2_1_26_1","first-page":"81","article-title":"A survey of performance measures for on-line algorithms","volume":"36","author":"Dorrigiv R.","year":"2005","unstructured":"{DLO05} R. Dorrigiv and A. L\u00f3pez-Ortiz . A survey of performance measures for on-line algorithms . SIGACT News , 36 ( 3 ):67{ 81 , September 2005 . {DLO05} R. Dorrigiv and A. L\u00f3pez-Ortiz. A survey of performance measures for on-line algorithms. SIGACT News, 36(3):67{81, September 2005.","journal-title":"SIGACT News"},{"key":"e_1_2_1_28_1","first-page":"215","volume-title":"Proc. CCCG","author":"Dorrigiv R.","year":"2008","unstructured":"{DLO08} R. Dorrigiv and A. L\u00f3pez-Ortiz . Adaptive searching in one and two dimensions . In Proc. CCCG , pages 215 - 218 , 2008 . {DLO08} R. Dorrigiv and A. L\u00f3pez-Ortiz. Adaptive searching in one and two dimensions. In Proc. CCCG, pages 215-218, 2008."},{"key":"e_1_2_1_29_1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BFb0029578","volume-title":"Online Algorithms -- The State of the Art","author":"Fiat A.","year":"1998","unstructured":"{FW98} A. Fiat and G. J. Woeginger . Competitive odds and ends . In A. Fiat and G. J. Woeginger, editors, Online Algorithms -- The State of the Art , volume 1442 of LNCS , pages 385 - 394 . Springer-Verlag , 1998 . {FW98} A. Fiat and G. J. Woeginger. Competitive odds and ends. In A. Fiat and G. J. Woeginger, editors, Online Algorithms -- The State of the Art, volume 1442 of LNCS, pages 385-394. Springer-Verlag, 1998."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/5505.5507"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799348670"},{"key":"e_1_2_1_32_1","volume-title":"Dissertation","author":"Icking Ch.","year":"1994","unstructured":"{Ick94} Ch. Icking . Motion and Visibility in Simple Polygons . Dissertation , Fernuniversit\u00e4t Hagen , 1994 . {Ick94} Ch. Icking. Motion and Visibility in Simple Polygons. Dissertation, Fernuniversit\u00e4t Hagen, 1994."},{"key":"e_1_2_1_33_1","first-page":"443","volume-title":"CCCG","author":"Icking Christian","year":"1993","unstructured":"{IKM93} Christian Icking , Rolf Klein , and Lihong Ma . How to look around a corner . In CCCG , pages 443 - 448 , 1993 . {IKM93} Christian Icking, Rolf Klein, and Lihong Ma. How to look around a corner. In CCCG, pages 443-448, 1993."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236353"},{"key":"e_1_2_1_35_1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/BFb0029564","volume-title":"Online Algorithms -- The State of the Art","author":"Irani S.","year":"1998","unstructured":"{Ira98} S. Irani . Competitive analysis of paging . In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms -- The State of the Art , volume 1442 of LNCS , pages 52 - 73 . 1998 . {Ira98} S. Irani. Competitive analysis of paging. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms -- The State of the Art, volume 1442 of LNCS, pages 52-73. 1998."},{"key":"e_1_2_1_36_1","first-page":"359","volume-title":"Proc. SODA","author":"Kenyon C.","year":"1996","unstructured":"{Ken96} C. Kenyon . Best-fit bin-packing with random order . In Proc. SODA , pages 359 - 364 , 1996 . {Ken96} C. Kenyon. Best-fit bin-packing with random order. In Proc. SODA, pages 359-364, 1996."},{"key":"e_1_2_1_37_1","first-page":"372","volume-title":"Proc. 5th SODA","author":"Kao M.-Y.","year":"1994","unstructured":"{KMSY94} M.-Y. Kao , Y. Ma , M. Sipser , and Y. Yin . Optimal constructions of hybrid algorithms . In Proc. 5th SODA , pages 372 - 381 , 1994 . {KMSY94} M.-Y. Kao, Y. Ma, M. Sipser, and Y. Yin. Optimal constructions of hybrid algorithms. In Proc. 5th SODA, pages 372-381, 1994."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299540"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268042"},{"key":"e_1_2_1_40_1","first-page":"441","volume-title":"Proc. 4th SODA","author":"Kao M.-Y.","year":"1993","unstructured":"{KRT93} M.-Y. Kao , J. H. Reif , and S. R. Tate . Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem . In Proc. 4th SODA , pages 441 - 447 , 1993 . {KRT93} M.-Y. Kao, J. H. Reif, and S. R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. In Proc. 4th SODA, pages 441-447, 1993."},{"key":"e_1_2_1_41_1","unstructured":"{Kru} P. Krugman. How i work. Available at: http:\/\/web.mit.edu\/krugman\/www\/howiwork.html.  {Kru} P. Krugman. How i work. Available at: http:\/\/web.mit.edu\/krugman\/www\/howiwork.html."},{"key":"e_1_2_1_43_1","volume-title":"AAAI","author":"L\u00f3pez-Ortiz Alejandro","year":"2006","unstructured":"{LOAH06} Alejandro L\u00f3pez-Ortiz , Spyros Angelopoulos , and Ang\u00e8le M. Hamel . Optimal scheduling of contract algorithms for anytime problems . In AAAI , 2006 . {LOAH06} Alejandro L\u00f3pez-Ortiz, Spyros Angelopoulos, and Ang\u00e8le M. Hamel. Optimal scheduling of contract algorithms for anytime problems. In AAAI, 2006."},{"key":"e_1_2_1_44_1","first-page":"1097","article-title":"Walking streets faster. In Proc. 5th SWAT, pages 345{356","author":"L\u00f3pez-Ortiz A.","year":"1996","unstructured":"{LOS96} A. L\u00f3pez-Ortiz and S. Schuierer . Walking streets faster. In Proc. 5th SWAT, pages 345{356 . LNCS 1097 , 1996 . {LOS96} A. L\u00f3pez-Ortiz and S. Schuierer. Walking streets faster. In Proc. 5th SWAT, pages 345{356. LNCS 1097, 1996.","journal-title":"LNCS"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00144-4"},{"key":"e_1_2_1_46_1","first-page":"125","volume-title":"CCCG","author":"L\u00f3pez-Ortiz Alejandro","year":"2001","unstructured":"{LOS01b} Alejandro L\u00f3pez-Ortiz and Graeme Sweet . Parallel searching on a lattice . In CCCG , pages 125 - 128 , 2001 . {LOS01b} Alejandro L\u00f3pez-Ortiz and Graeme Sweet. Parallel searching on a lattice. In CCCG, pages 125-128, 2001."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/645901.672766"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.08.001"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542412"},{"key":"e_1_2_1_50_1","volume-title":"Cache-oblivious algorithms. Master's thesis","author":"Prokop H.","year":"1999","unstructured":"{Pro99} H. Prokop . Cache-oblivious algorithms. Master's thesis , Massachusetts Institute of Technology , Dept . of Electrical Engineering and Computer Science, 1999 . {Pro99} H. Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1999."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132587"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800180202"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294261"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/646341.686576"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009192"},{"key":"e_1_2_1_58_1","unstructured":"{Uni} New Mexico State University. Homepage of new mexico state university tracebase (online). Available at: http:\/\/tracebase.nmsu.edu\/tracebase.html.  {Uni} New Mexico State University. Homepage of new mexico state university tracebase (online). Available at: http:\/\/tracebase.nmsu.edu\/tracebase.html."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_2_1_60_1","first-page":"420","volume-title":"Proc. SODA","author":"Young N. E.","year":"1998","unstructured":"{You98} N. E. Young . Bounding the diffuse adversary . In Proc. SODA , pages 420 - 425 , 1998 . {You98} N. E. Young. Bounding the diffuse adversary. In Proc. SODA, pages 420-425, 1998."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1099"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0124-5"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1711475.1711499","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=1711499&amp;ftid=736005&amp;dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:35Z","timestamp":1750250495000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1711475.1711499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,25]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1,25]]}},"alternative-id":["10.1145\/1711475.1711499"],"URL":"https:\/\/doi.org\/10.1145\/1711475.1711499","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2010,1,25]]},"assertion":[{"value":"2010-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}