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:








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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 02:40:19 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section