{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,15]],"date-time":"2026-02-15T08:46:56Z","timestamp":1771145216208,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2006,12,1]],"date-time":"2006-12-01T00:00:00Z","timestamp":1164931200000},"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":[[2006,12]]},"abstract":"<jats:p>We discuss what we refer to, tentatively, as the \"doubling\" method for designing online and offline approximation algorithms. The rough idea is to use geometrically increasing estimates on the optimal solution to produce fragments of the algorithm's solution. The term \"doubling\" is a little misleading, for often factors other than 2 are used, and suggestions for a better name will be appreciated.<\/jats:p>","DOI":"10.1145\/1189056.1189078","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"115-126","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["SIGACT news online algorithms column 10"],"prefix":"10.1145","volume":"37","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"University of California, Riverside"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Kenyon-Mathieu","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0092"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258201"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1054"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1425(200009\/10)3:5<259::AID-JOS47>3.0.CO;2-3"},{"key":"e_1_2_1_6_1","first-page":"221","article-title":"On the linear search problem","volume":"2","author":"Beck A.","year":"1964","unstructured":"A. Beck . On the linear search problem . Naval Research Logistics Quarterly , 2 : 221 -- 228 , 1964 . A. Beck. On the linear search problem. Naval Research Logistics Quarterly, 2:221--228, 1964.","journal-title":"Naval Research Logistics Quarterly"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1005070"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1070"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195125"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/237502.237577"},{"key":"e_1_2_1_11_1","series-title":"Lecture Notes in Comput","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/3-540-61440-0_166","volume-title":"Proc. 23rd International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Chakrabarti S.","year":"1996","unstructured":"S. Chakrabarti , C. A. Phillips , A. S. Schulz , D. B. Shmoys , C. Stein , and J. Wein . Improved scheduling algorithms for minsum criteria . In Proc. 23rd International Colloquium on Automata, Languages, and Programming (ICALP) , volume 1099 of Lecture Notes in Comput . Sci., pages 646 -- 657 . Springer , 1996 . S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein. Improved scheduling algorithms for minsum criteria. In Proc. 23rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 1099 of Lecture Notes in Comput. Sci., pages 646--657. Springer, 1996."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258657"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946316"},{"key":"e_1_2_1_14_1","first-page":"609","volume-title":"Proc. 8th Symp. on Discrete Algorithms (SODA)","author":"Chekuri C.","year":"1997","unstructured":"C. Chekuri , R. Motwani , B. Natarajan , and C. Stein . Approximation techniques for average completion time scheduling . In Proc. 8th Symp. on Discrete Algorithms (SODA) , pages 609 -- 618 . ACM\/SIAM, 1997 . C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. In Proc. 8th Symp. on Discrete Algorithms (SODA), pages 609--618. ACM\/SIAM, 1997."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_31"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0987"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11970125_11"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.006"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.018"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_31"},{"key":"e_1_2_1_22_1","volume-title":"Search Games","author":"Gal S.","year":"1980","unstructured":"S. Gal . Search Games . Academic Press , 1980 . S. Gal. Search Games. Academic Press, 1980."},{"key":"e_1_2_1_23_1","first-page":"152","volume-title":"Proc. 7th Symp. on Discrete Algorithms (SODA)","author":"Goemans M.","year":"1996","unstructured":"M. Goemans and J. Kleinberg . An improved approximation ratio for the minimum latency problem . In Proc. 7th Symp. on Discrete Algorithms (SODA) , pages 152 -- 158 . ACM\/SIAM, 1996 . M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. In Proc. 7th Symp. on Discrete Algorithms (SODA), pages 152--158. ACM\/SIAM, 1996."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585867"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_27_1","first-page":"142","volume-title":"Proc. 7th Symp. on Discrete Algorithms (SODA)","author":"Hall L.","year":"1996","unstructured":"L. Hall , D. Shmoys , and J. Wein . Scheduling to minimize average completion time: Off-line and on-line algorithms . In Proc. 7th Symp. on Discrete Algorithms (SODA) , pages 142 -- 151 . ACM\/SIAM, 1996 . L. Hall, D. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Proc. 7th Symp. on Discrete Algorithms (SODA), pages 142--151. ACM\/SIAM, 1996."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.3.513"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645587.659604"},{"key":"e_1_2_1_30_1","first-page":"441","volume-title":"Proc. 4th Symp. on Discrete Algorithms (SODA)","author":"Kao M.-Y.","year":"1993","unstructured":"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 Symp. on Discrete Algorithms (SODA) , pages 441 -- 447 . ACM\/SIAM, 1993 . 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 Symp. on Discrete Algorithms (SODA), pages 441--447. ACM\/SIAM, 1993."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109684"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796586"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383443"},{"key":"e_1_2_1_34_1","first-page":"422","volume-title":"Proc. 4th Symp. on Discrete Algorithms (SODA)","author":"Motwani R.","year":"1993","unstructured":"R. Motwani , S. Phillips , and E. Torng . Non-clairvoyant scheduling . In Proc. 4th Symp. on Discrete Algorithms (SODA) , pages 422 -- 431 . ACM\/SIAM, 1993 . R. Motwani, S. Phillips, and E. Torng. Non-clairvoyant scheduling. In Proc. 4th Symp. on Discrete Algorithms (SODA), pages 422--431. ACM\/SIAM, 1993."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90263-2"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.660083"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189056.1189078","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189056.1189078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:51:31Z","timestamp":1750258291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189056.1189078"}},"subtitle":["competitiveness via doubling"],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189056.1189078"],"URL":"https:\/\/doi.org\/10.1145\/1189056.1189078","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}