English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

Incremental Algorithms for Facility Location and k-Median

MPS-Authors
/persons/resource/persons44436

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

/persons/resource/persons43989

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

Radzik,  Tomasz
Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2932-1
Abstract
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.