de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

##### MPS-Authors

Mestre,  Julián
Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

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: http://hdl.handle.net/11858/00-001M-0000-000F-1AC6-0
##### Abstract
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.