Back to Search
Start Over
ADAPTIVE LOCAL RATIO.
- Source :
-
SIAM Journal on Computing . 2010, Vol. 39 Issue 7, p3038-3057. 20p. 4 Diagrams, 1 Chart. - Publication Year :
- 2010
-
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 models. Guided by this process, a solution S is constructed such that S is a-approximate with respect to each model used in the decomposition. As a result, S is a-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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 39
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 52932678
- Full Text :
- https://doi.org/10.1137/080731712