de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Adaptive Local Ratio

MPG-Autoren

Mestre,  Julián
Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


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