Online facility location
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 426-431
- https://doi.org/10.1109/sfcs.2001.959917
Abstract
We consider the online variant of facility location, in which demand points arrive one at a time and we must maintain a set of facilities to service these points. We provide a randomized online O(1)-competitive algorithm in the case where points arrive in random order. If points are ordered adversarially, we show that no algorithm can be constant-competitive, and provide an O(log n)-competitive algorithm. Our algorithms are randomized and the analysis depends heavily on the concept of expected waiting time. We also combine our techniques with those of M. Charikar and S. Guha (1999) to provide a linear-time constant approximation for the offline facility location problem.Keywords
This publication has 8 references indexed in Scilit:
- Improved combinatorial algorithms for the facility location and k-median problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Primal-dual approximation algorithms for metric facility location and k-median problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- The online median problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Local search heuristic for k-median and facility location problemsPublished by Association for Computing Machinery (ACM) ,2001
- Facility location with nonuniform hard capacitiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- A constant-factor approximation algorithm for the k -median problem (extended abstract)Published by Association for Computing Machinery (ACM) ,1999
- Improved Approximation Algorithms for Capacitated Facility Location ProblemsPublished by Springer Nature ,1999
- Improved Approximation Algorithms for Uncapacitated Facility LocationPublished by Springer Nature ,1998