Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Adaptive Local Ratio

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.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1AC6-0 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1AC7-E
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Mestre, Julián1, Autor
Affiliations:
1Max Planck Society, ou_persistent13              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2009-03-262008
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: New York, NY : ACM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 428165
URI: http://portal.acm.org/ft_gateway.cfm?id=1347099&type=pd
Anderer: Local-ID: C125756E0038A185-50F3F35FC21C5964C125745E00459C0A-conf/soda/Mestre2008
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: San Francisco, USA
Start-/Enddatum: 2008-01-20 - 2008-01-22

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, NY : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 152 - 160 Identifikator: ISBN: 978-0-89871-647-4