SIGACT news online algorithms column 10: competitiveness via doubling. Chrobak, M. & Kenyon-Mathieu, C. SIGACT News, 37(4):115--126, 2006.
SIGACT news online algorithms column 10: competitiveness via doubling [link]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