SIGACT news online algorithms column 10
Marek Chrobák, Claire M. Kenyon-Mathieu · ACM SIGACT News · 2006
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.