MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mestre, Juliándblp
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
Conference URL::
Downloading URL:
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:
Note, Abstract, ©
(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},
 TITLE = {Adaptive Local Ratio},
 BOOKTITLE = {19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
 PUBLISHER = {Society for Industrial and Applied Mathematics},
 YEAR = {2008},
 PAGES = {152--160},
 ADDRESS = {San Francisco, USA},
 MONTH = {January},
}

Entry last modified by Julian Mestre, 02/07/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Julian Mestre		Created
06/04/2008 14:40:19
Revisions
5.
4.
3.
2.
1.		Editor(s)
Julian Mestre
Uwe Brahm
Julian Mestre
Julian Mestre
Julian Mestre		Edit Dates
02/07/2009 10:36:51 AM
01/20/2009 07:20:18 PM
01/14/2009 03:52:51 PM
01/14/2009 03:51:52 PM
06/04/2008 03:00:53 PM