Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Adaptive Local Ratio


Mestre,  Julián
Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Mestre, J. (2008). Adaptive Local Ratio. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008 (pp. 152-160). New York, NY: ACM.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1AC6-0
Local Ratio is a well-known paradigm for designing approximation algorithms for combinatorial optimization problems. At a very high level, a local ratio algorithm first decomposes the input weight function $w$ into a positive linear combination of simpler weight functions or \emph{models}. Guided by this process a solution $S$ is constructed such that $S$ is $\alpha$-approximate with respect to each model used in the decomposition. As a result, $S$ is $\alpha$-approximate under $w$ as well. These models usually have a very simple structure that remains ``unchanged'' throughout the execution of the algorithm. In this work we show that adaptively choosing a model from a richer spectrum of functions can lead to a better local ratio. Indeed, by turning the search for a good model into an optimization problem of its own, we get improved approximations for a data migration problem.