Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Mestre, Julián dblp
 Editor(s):
 BibTeX cite key*: conf/soda/Mestre2008

 Title, Booktitle
 Title*: Adaptive Local Ratio Booktitle*: 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

 Event, URLs
 URL of the conference: URL for downloading the paper: http://portal.acm.org/ft_gateway.cfm?id=1347099&type=pd Event Address*: San Francisco, USA Language: English Event Date* (no longer used): Organization: Event Start Date: 20 January 2008 Event End Date: 22 January 2008

 Publisher
 Name*: Society for Industrial and Applied Mathematics URL: http://www.siam.org Address*: Philadelphia, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: January Pages: 152-160 Year*: 2008 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (LaTeX) 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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: popular Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{conf/soda/Mestre2008,
AUTHOR = {Mestre, Juli{\'a}n},