{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:43:06Z","timestamp":1774590186835,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"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":[[2005,9]]},"abstract":"<jats:p>Pros and cons of the competitive analysis have been discussed in the literature by many authors. Continuing this discussion in this quarter s column, Reza Dorrigiv and Alejandro Lopez-Ortiz review and compare various performance measures for online algorithms, highlighting their differences with respect to the competitive ratio. Many thanks to Reza and Alejandro for contributing this article.<\/jats:p>","DOI":"10.1145\/1086649.1086670","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T19:28:32Z","timestamp":1131391712000},"page":"67-81","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["SIGACT news online algorithms column 8"],"prefix":"10.1145","volume":"36","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"University of California, Riverside"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645900.672599"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022985808959"},{"key":"e_1_2_1_3_1","volume-title":"Guo-Hui Lin. Better Bounds on the Accommodating Ratio for the Seat Reservation Problem. In Sixth Annual International Computing and Combinatorics Conference","volume":"1858","author":"Bach Eric","year":"2000","unstructured":"{BBJ+00} Eric Bach , Joan Boyar , Tao Jiang , Kim S. Larsen , and Guo-Hui Lin. Better Bounds on the Accommodating Ratio for the Seat Reservation Problem. In Sixth Annual International Computing and Combinatorics Conference , volume 1858 of Lecture Notes in Computer Science, pages 221--231. Springer-Verlag , 2000 .]] {BBJ+00} Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, and Guo-Hui Lin. Better Bounds on the Accommodating Ratio for the Seat Reservation Problem. In Sixth Annual International Computing and Combinatorics Conference, volume 1858 of Lecture Notes in Computer Science, pages 221--231. Springer-Verlag, 2000.]]"},{"key":"e_1_2_1_4_1","first-page":"905","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02)","author":"Blum Avrim","year":"2002","unstructured":"{BD02} Avrim Blum and John Dunagan . Smoothed analysis of the perceptron algorithm for linear programming . In Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02) , pages 905 -- 914 , 2002 .]] {BD02} Avrim Blum and John Dunagan. Smoothed analysis of the perceptron algorithm for linear programming. In Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02), pages 905--914, 2002.]]"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294264"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1757536.1757552"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070534"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-003-0124-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1021"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.02.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009286"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946319"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361786"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45138-9_14"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/363011.363155"},{"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.5555\/896971.896976"},{"key":"e_1_2_1_22_1","first-page":"63","volume-title":"Proc. 8th Symp. on Discrete Algorithms (SODA)","author":"Fiat Amos","year":"1997","unstructured":"{FR97} Amos Fiat and Ziv Rosen . Experimental studies of access graph based heuristics: Beating the LRU standard ? In Proc. 8th Symp. on Discrete Algorithms (SODA) , pages 63 -- 72 . ACM\/SIAM, 1997 .]] {FR97} Amos Fiat and Ziv Rosen. Experimental studies of access graph based heuristics: Beating the LRU standard? In Proc. 8th Symp. on Discrete Algorithms (SODA), pages 63--72. ACM\/SIAM, 1997.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622467.1622486"},{"key":"e_1_2_1_24_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 Amos","year":"1998","unstructured":"{FW98} Amos Fiat and Gerhard J. Woeginger . Competitive odds and ends . In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms --- The State of the Art , volume 1442 of LNCS , pages 385 -- 394 . Springer-Verlag , 1998 .]] {FW98} Amos Fiat and Gerhard J. Woeginger. Competitive odds and ends. In Amos Fiat and Gerhard 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_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0317009"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236353"},{"key":"e_1_2_1_27_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 Sandy","year":"1998","unstructured":"{Ira98} Sandy 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 . Springer-Verlag , 1998 .]] {Ira98} Sandy 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. Springer-Verlag, 1998.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/313852.314083"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796244"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299540"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/3-540-61440-0_135","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Koutsoupias Elias","year":"1996","unstructured":"{KPY96} Elias Koutsoupias , Christos Papadimitriou , and Mihalis Yannakakis . Searching a fixed graph . In International Colloquium on Automata, Languages, and Programming , volume 1099 , pages 280 -- 289 , 1996 .]] {KPY96} Elias Koutsoupias, Christos Papadimitriou, and Mihalis Yannakakis. Searching a fixed graph. In International Colloquium on Automata, Languages, and Programming, volume 1099, pages 280--289, 1996.]]"},{"key":"e_1_2_1_33_1","volume-title":"Lubeck","author":"Manthey Bodo","year":"2005","unstructured":"{MR05} Bodo Manthey and Rudiger Reischuk . Smoothed analysis of the height of binary search trees. Schriftenreihe der Institute fur Informatik und Mathematik A-05-17, Universitat zu Lubeck , Lubeck , June 2005 .]] {MR05} Bodo Manthey and Rudiger Reischuk. Smoothed analysis of the height of binary search trees. Schriftenreihe der Institute fur Informatik und Mathematik A-05-17, Universitat zu Lubeck, Lubeck, June 2005.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_35_1","volume-title":"Spielman and Shang-Hua Teng. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming, 97(1--2):375--404","author":"Daniel","year":"2003","unstructured":"{ST03} Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming, 97(1--2):375--404 , 2003 .]] {ST03} Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming, 97(1--2):375--404, 2003.]]"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/314613.314772"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1099"},{"key":"e_1_2_1_40_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\/1086649.1086670","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1086649.1086670","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:13Z","timestamp":1750262893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1086649.1086670"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1086649.1086670"],"URL":"https:\/\/doi.org\/10.1145\/1086649.1086670","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}