{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:58Z","timestamp":1759637818846,"version":"3.41.0"},"reference-count":102,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"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":[[2008,9]]},"abstract":"<jats:p>This is a survey of last year's work on online competitive algorithms. The survey covers only conference papers, including those from SODA, FOCS, STOC, STACS, COCOON, ISAAC, ESA, ICALP, WAOA, and ISAAC. I tried to focus on research directly dealing with competitive analysis, and in many cases I had to make judgment calls, whether to include them or not. My initial intent was to cover only some highlights, representative of the current trends in the field, but somehow, over time, it grew to a much longer and comprehensive document. I feel compelled to add that, with the deadline approaching, I was not able to spend as much time on debugging as I should, and some errors and omissions are, I'm afraid, inevitable. If you spot anything that should be corrected, please let me know.<\/jats:p>","DOI":"10.1145\/1412700.1412719","type":"journal-article","created":{"date-parts":[[2008,9,23]],"date-time":"2008-09-23T13:37:59Z","timestamp":1222177079000},"page":"96-121","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["SIGACT news online algorithms column 13"],"prefix":"10.1145","volume":"39","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":[[2008,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"e_1_2_1_2_1","first-page":"771","volume-title":"Proc. 14th Symp. on Discrete Algorithms (SODA)","author":"Aiello W. A.","year":"2003","unstructured":"W. A. Aiello , R. Ostrovsky , E. Kyshilevitz , and A. Rosen . Dynamic routing on networks with fixed-size buffers . In Proc. 14th Symp. on Discrete Algorithms (SODA) , pages 771 -- 780 . ACM\/SIAM, 2003 . W. A. Aiello, R. Ostrovsky, E. Kyshilevitz, and A. Rosen. Dynamic routing on networks with fixed-size buffers. In Proc. 14th Symp. on Discrete Algorithms (SODA), pages 771--780. ACM\/SIAM, 2003."},{"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.1145\/1290672.1290686"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778649"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248424"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007366"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334221"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993249195"},{"key":"e_1_2_1_10_1","first-page":"761","volume-title":"Proc. 14th Symp. on Discrete Algorithms (SODA)","author":"Andelman N.","year":"2003","unstructured":"N. Andelman , Y. Mansour , and A. Zhu . Competitive queueing policies in QoS switches . In Proc. 14th Symp. on Discrete Algorithms (SODA) , pages 761 -- 770 . ACM\/SIAM, 2003 . N. Andelman, Y. Mansour, and A. Zhu. Competitive queueing policies in QoS switches. In Proc. 14th Symp. on Discrete Algorithms (SODA), pages 761--770. ACM\/SIAM, 2003."},{"key":"e_1_2_1_11_1","first-page":"248","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Angelopoulos S.","year":"2007","unstructured":"S. Angelopoulos . Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 248 -- 257 , 2007 . S. Angelopoulos. Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 248--257, 2007."},{"key":"e_1_2_1_12_1","first-page":"229","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Angelopoulos S.","year":"2007","unstructured":"S. Angelopoulos , R. Dorrigiv , and A. L\u00f3pez-Ortiz . On the separation and equivalence of paging strategies . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 229 -- 237 , 2007 . S. Angelopoulos, R. Dorrigiv, and A. L\u00f3pez-Ortiz. On the separation and equivalence of paging strategies. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 229--237, 2007."},{"key":"e_1_2_1_13_1","first-page":"814","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Aspnes J.","year":"2007","unstructured":"J. Aspnes , Y. R. Yang , and Y. Yin . Path-independent load balancing with unreliable machines . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 814 -- 823 , 2007 . J. Aspnes, Y. R. Yang, and Y. Yin. Path-independent load balancing with unreliable machines. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 814--823, 2007."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248431"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"e_1_2_1_17_1","first-page":"434","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Babaioff M.","year":"2007","unstructured":"M. Babaioff , N. Immorlica , and R. Kleinberg . Matroids, secretary problems, and online mechanisms . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 434 -- 443 , 2007 . M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 434--443, 2007."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778629"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394546"},{"key":"e_1_2_1_21_1","first-page":"726","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Bansal N.","year":"2007","unstructured":"N. Bansal , N. Chen , N. Cherniavsky , A. Rudra , B. Schieber , and M. Sviridenko . Dynamic pricing for impatient bidders . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 726 -- 735 , 2007 . N. Bansal, N. Chen, N. Cherniavsky, A. Rudra, B. Schieber, and M. Sviridenko. Dynamic pricing for impatient bidders. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 726--735, 2007."},{"key":"e_1_2_1_22_1","first-page":"805","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Bansal N.","year":"2007","unstructured":"N. Bansal , K. Pruhs , and C. Stein . Speed scaling for weighted flow time . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 805 -- 813 , 2007 . N. Bansal, K. Pruhs, and C. Stein. Speed scaling for weighted flow time. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 805--813, 2007."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394568"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248409"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-68530-8_21","volume-title":"Proc. 6th European Symp. on Algorithms (ESA)","author":"Bartal Y.","year":"1998","unstructured":"Y. Bartal , M. Chrobak , and L. L. Larmore . A randomized algorithm for two servers on the line . In Proc. 6th European Symp. on Algorithms (ESA) , Lecture Notes in Comput. Sci. , pages 247 -- 258 . Springer , 1998 . Y. Bartal, M. Chrobak, and L. L. Larmore. A randomized algorithm for two servers on the line. In Proc. 6th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci., pages 247--258. Springer, 1998."},{"key":"e_1_2_1_26_1","first-page":"246","volume-title":"Proc. 5thInternational Workshop in Approximation and Online Algorithms","author":"Bein W. W.","year":"2007","unstructured":"W. W. Bein , K. Iwama , J. Kawahara , L. L. Larmore , and J. A. Oravec . A randomized algorithm for two servers in cross polytope spaces . In Proc. 5thInternational Workshop in Approximation and Online Algorithms , pages 246 -- 259 , 2007 . W. W. Bein, K. Iwama, J. Kawahara, L. L. Larmore, and J. A. Oravec. A randomized algorithm for two servers in cross polytope spaces. In Proc. 5thInternational Workshop in Approximation and Online Algorithms, pages 246--259, 2007."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778620"},{"key":"e_1_2_1_28_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998","unstructured":"A. Borodin and R. El-Yaniv . Online Computation and Competitive Analysis . Cambridge University Press , 1998 . A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778606"},{"key":"e_1_2_1_30_1","first-page":"795","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Chan H.-L.","year":"2007","unstructured":"H.-L. Chan , W.-T. Chan , T. W. Lam , L.-K. Lee , K.-S. Mak , and P. W. H. Wong . Energy efficient online deadline scheduling . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 795 -- 804 , 2007 . H.-L. Chan, W.-T. Chan, T. W. Lam, L.-K. Lee, K.-S. Mak, and P. W. H. Wong. Energy efficient online deadline scheduling. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 795--804, 2007."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248418"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11970125_10"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418498"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.03.005"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1025-6"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1781574.1781626"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394650.2394701"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/992287.992304"},{"key":"e_1_2_1_39_1","first-page":"207","volume-title":"Proc. 5thInternational Workshop in Approximation and Online Algorithms","author":"Chrobak M.","year":"2007","unstructured":"M. Chrobak and M. Hurand . Better bounds for incremental medians . In Proc. 5thInternational Workshop in Approximation and Online Algorithms , pages 207 -- 217 , 2007 . M. Chrobak and M. Hurand. Better bounds for incremental medians. In Proc. 5thInternational Workshop in Approximation and Online Algorithms, pages 207--217, 2007."},{"key":"e_1_2_1_40_1","first-page":"115","volume-title":"SIGACT News","author":"Chrobak M.","year":"2006","unstructured":"M. Chrobak and C. Kenyon . Competitiveness via doubling . SIGACT News , pages 115 -- 126 , 2006 . M. Chrobak and C. Kenyon. Competitiveness via doubling. SIGACT News, pages 115--126, 2006."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_31"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00099-9"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778621"},{"key":"e_1_2_1_44_1","unstructured":"R. Dorrigiv and A. L\u00f3pez-Ortiz. A survey of performance measures for on-line algorithms. SIGACT News 36(3).  R. Dorrigiv and A. L\u00f3pez-Ortiz. A survey of performance measures for on-line algorithms. SIGACT News 36(3)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1781574.1781629"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077467"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250871"},{"key":"e_1_2_1_48_1","first-page":"209","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Englert M.","year":"2007","unstructured":"M. Englert and M. Westerman . Considering suppressed packets improves buffer management in QoS switches . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 209 -- 218 . ACM\/SIAM, 2007 . M. Englert and M. Westerman. Considering suppressed packets improves buffer management in QoS switches. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 209--218. ACM\/SIAM, 2007."},{"key":"e_1_2_1_49_1","first-page":"142","volume-title":"Proc. 5thInternational Workshop in Approximation and Online Algorithms","author":"Epstein L.","year":"2007","unstructured":"L. Epstein and A. Levin . On the max coloring problem . In Proc. 5thInternational Workshop in Approximation and Online Algorithms , pages 142 -- 155 , 2007 . L. Epstein and A. Levin. On the max coloring problem. In Proc. 5thInternational Workshop in Approximation and Online Algorithms, pages 142--155, 2007."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027914.1027930"},{"key":"e_1_2_1_51_1","first-page":"193","volume-title":"Proc. 5thInternational Workshop in Approximation and Online Algorithms","author":"Epstein L.","year":"2007","unstructured":"L. Epstein and R. van Stee . On the online unit clustering problem . In Proc. 5thInternational Workshop in Approximation and Online Algorithms , pages 193 -- 206 , 2007 . L. Epstein and R. van Stee. On the online unit clustering problem. In Proc. 5thInternational Workshop in Approximation and Online Algorithms, pages 193--206, 2007."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_24"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102001527"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778631"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.015"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394650.2394669"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763424.1763502"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_61_1","first-page":"1164","volume-title":"Proc. 16th Symp. on Discrete Algorithms (SODA)","author":"Guruswami V.","year":"2005","unstructured":"V. Guruswami , J. D. Hartline , A. R. Karlin , D. Kempe , C. Kenyon , and F. McSherry . On profit-maximizing envy-free pricing . In Proc. 16th Symp. on Discrete Algorithms (SODA) , pages 1164 -- 1173 . ACM\/SIAM, 2005 . V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On profit-maximizing envy-free pricing. In Proc. 16th Symp. on Discrete Algorithms (SODA), pages 1164--1173. ACM\/SIAM, 2005."},{"key":"e_1_2_1_62_1","first-page":"434","volume-title":"Conference in Information Sciences and Systems","author":"Hajek B.","year":"2001","unstructured":"B. Hajek . On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time . In Conference in Information Sciences and Systems , pages 434 -- 438 , 2001 . B. Hajek. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In Conference in Information Sciences and Systems, pages 434--438, 2001."},{"key":"e_1_2_1_63_1","first-page":"929","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Hajiaghayi M. T.","year":"2007","unstructured":"M. T. Hajiaghayi , R. Kleinberg , and T. Leighton . Semi-oblivious routing: lower bounds . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 929 -- 938 , 2007 . M. T. Hajiaghayi, R. Kleinberg, and T. Leighton. Semi-oblivious routing: lower bounds. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 929--938, 2007."},{"key":"e_1_2_1_64_1","first-page":"782","volume-title":"Proc. 16th Symp. on Discrete Algorithms (SODA)","author":"Hajiaghayi M. T.","year":"2005","unstructured":"M. T. Hajiaghayi , R. D. Kleinberg , T. Leighton , and H. R\u00e4cke . Oblivious routing on node-capacitated and directed graphs . In Proc. 16th Symp. on Discrete Algorithms (SODA) , pages 782 -- 790 . ACM\/SIAM, 2005 . M. T. Hajiaghayi, R. D. Kleinberg, T. Leighton, and H. R\u00e4cke. Oblivious routing on node-capacitated and directed graphs. In Proc. 16th Symp. on Discrete Algorithms (SODA), pages 782--790. ACM\/SIAM, 2005."},{"key":"e_1_2_1_65_1","first-page":"69","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Han Q.","year":"2007","unstructured":"Q. Han , D. Du , J. Vera , and L. F. Zuluaga . Improved bounds for the symmetric rendezvous value on the line . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 69 -- 78 , 2007 . Q. Han, D. Du, J. Vera, and L. F. Zuluaga. Improved bounds for the symmetric rendezvous value on the line. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 69--78, 2007."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/1787680.1787686"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067324"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.758841"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_13"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1068"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250870"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_48"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90042-6"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248437"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778624"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.5555\/1781574.1781628"},{"key":"e_1_2_1_80_1","first-page":"199","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Li F.","year":"2007","unstructured":"F. Li , J. Sethuraman , and C. Stein . Better online buffer management . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 199 -- 208 , 2007 . F. Li, J. Sethuraman, and C. Stein. Better online buffer management. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 199--208, 2007."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109684"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_2_1_83_1","first-page":"382","volume-title":"Proc. 5th Symp. on Discrete Algorithms (SODA)","author":"Lund C.","year":"1994","unstructured":"C. Lund and N. Reingold . Linear programs for randomized on-line algorithms . In Proc. 5th Symp. on Discrete Algorithms (SODA) , pages 382 -- 391 . ACM\/SIAM, 1994 . C. Lund and N. Reingold. Linear programs for randomized on-line algorithms. In Proc. 5th Symp. on Discrete Algorithms (SODA), pages 382--391. ACM\/SIAM, 1994."},{"key":"e_1_2_1_84_1","first-page":"486","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Marciniszyn M.","year":"2007","unstructured":"M. Marciniszyn and R. Sp\u00f6hel . Online vertex colorings of random graphs without monochromatic subgraphs . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 486 -- 493 , 2007 . M. Marciniszyn and R. Sp\u00f6hel. Online vertex colorings of random graphs without monochromatic subgraphs. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 486--493, 2007."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.12"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72870-2_12"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383443"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109662"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOSH.0000031423.39762.d3"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652152"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778648"},{"key":"e_1_2_1_95_1","first-page":"238","volume-title":"Proc. 18th Symp. on Discrete Algorithms (SODA)","author":"Robert J.","year":"2007","unstructured":"J. Robert and N. Schabanel . Pull-based data broadcast with dependencies: be fair to users, not to items . In Proc. 18th Symp. on Discrete Algorithms (SODA) , pages 238 -- 247 , 2007 . J. Robert and N. Schabanel. Pull-based data broadcast with dependencies: be fair to users, not to items. In Proc. 18th Symp. on Discrete Algorithms (SODA), pages 238--247, 2007."},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248430"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_24"},{"key":"e_1_2_1_99_1","first-page":"274","volume-title":"Proc. 5thInternational Workshop in Approximation and Online Algorithms","author":"Wang H.","year":"2007","unstructured":"H. Wang , A. Chaudhary , and D. Z. Chen . Online rectangle filling . In Proc. 5thInternational Workshop in Approximation and Online Algorithms , pages 274 -- 287 , 2007 . H. Wang, A. Chaudhary, and D. Z. Chen. Online rectangle filling. In Proc. 5thInternational Workshop in Approximation and Online Algorithms, pages 274--287, 2007."},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90150-3"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-007-0032-x"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394650.2394688"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412700.1412719","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412700.1412719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412700.1412719"}},"subtitle":["2007 - an offine perspective"],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":102,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1145\/1412700.1412719"],"URL":"https:\/\/doi.org\/10.1145\/1412700.1412719","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2008,9]]},"assertion":[{"value":"2008-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}