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

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Incremental Algorithms for Facility Location and k-Median

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44436

Fotakis,  Dimitris
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Radzik,  Tomasz
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

Fotakis, D. (2004). Incremental Algorithms for Facility Location and k-Median. In Algorithms – ESA 2004: 12th Annual European Symposium (pp. 347-358). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2932-1
Zusammenfassung
In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing cluster or placing it in a new singleton cluster. The algorithm can also merge some of the existing clusters at any point in time. We present the first incremental algorithm for Facility Location with uniform facility costs which achieves a constant performance ratio and the first incremental algorithm for k-Median which achieves a constant performance ratio using O(k) medians.