SIGACT news online algorithms column 10: competitiveness via doubling. Chrobak, M. & Kenyon-Mathieu, C. SIGACT News, 37(4):115--126, 2006. Paper doi abstract bibtex 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.
@article{chrobak_sigact_2006,
title = {{SIGACT} news online algorithms column 10: competitiveness via doubling},
volume = {37},
shorttitle = {{SIGACT} news online algorithms column 10},
url = {http://portal.acm.org/citation.cfm?id=1189078},
doi = {10.1145/1189056.1189078},
abstract = {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.},
number = {4},
urldate = {2009-03-26TZ},
journal = {SIGACT News},
author = {Chrobak, Marek and Kenyon-Mathieu, Claire},
year = {2006},
pages = {115--126}
}
Downloads: 0
{"_id":"mEsTvDL7srpZPifcd","bibbaseid":"chrobak-kenyonmathieu-sigactnewsonlinealgorithmscolumn10competitivenessviadoubling-2006","downloads":0,"creationDate":"2016-12-19T20:50:58.843Z","title":"SIGACT news online algorithms column 10: competitiveness via doubling","author_short":["Chrobak, M.","Kenyon-Mathieu, C."],"year":2006,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"SIGACT news online algorithms column 10: competitiveness via doubling","volume":"37","shorttitle":"SIGACT news online algorithms column 10","url":"http://portal.acm.org/citation.cfm?id=1189078","doi":"10.1145/1189056.1189078","abstract":"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.","number":"4","urldate":"2009-03-26TZ","journal":"SIGACT News","author":[{"propositions":[],"lastnames":["Chrobak"],"firstnames":["Marek"],"suffixes":[]},{"propositions":[],"lastnames":["Kenyon-Mathieu"],"firstnames":["Claire"],"suffixes":[]}],"year":"2006","pages":"115--126","bibtex":"@article{chrobak_sigact_2006,\n\ttitle = {{SIGACT} news online algorithms column 10: competitiveness via doubling},\n\tvolume = {37},\n\tshorttitle = {{SIGACT} news online algorithms column 10},\n\turl = {http://portal.acm.org/citation.cfm?id=1189078},\n\tdoi = {10.1145/1189056.1189078},\n\tabstract = {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.},\n\tnumber = {4},\n\turldate = {2009-03-26TZ},\n\tjournal = {SIGACT News},\n\tauthor = {Chrobak, Marek and Kenyon-Mathieu, Claire},\n\tyear = {2006},\n\tpages = {115--126}\n}\n\n","author_short":["Chrobak, M.","Kenyon-Mathieu, C."],"key":"chrobak_sigact_2006","id":"chrobak_sigact_2006","bibbaseid":"chrobak-kenyonmathieu-sigactnewsonlinealgorithmscolumn10competitivenessviadoubling-2006","role":"author","urls":{"Paper":"http://portal.acm.org/citation.cfm?id=1189078"},"downloads":0,"html":""},"search_terms":["sigact","news","online","algorithms","column","competitiveness","via","doubling","chrobak","kenyon-mathieu"],"keywords":[],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}