Facility Location with Dynamic Distance Functions

Randeep Bhatia*, Sudipto Guha, Samir Khuller, Yoram J. Sussmann

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Facility location problems have always been studied with the assumption that the edge lengths in the network are static and do not change over time. The underlying network could be used to model a city street network for emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to traffic congestion the traversal time on links changes with time. Very often, we have estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) as centers, such that at every time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results for the K-center problem under this model. This is the first comprehensive study regarding approximation algorithms for facility location for good time-invariant solutions.

Original languageEnglish (US)
Pages (from-to)199-217
Number of pages19
JournalJournal of Combinatorial Optimization
Volume2
Issue number3
DOIs
StatePublished - 1998

Keywords

  • Approximation algorithms
  • Facility location
  • Graph algorithms
  • K-center problem

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Facility Location with Dynamic Distance Functions'. Together they form a unique fingerprint.

Cite this