Facility location with dynamic functions distance

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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 Kcenter problem under this model. This is the first comprehensive study regarding approximation algorithms for facility location for good timeinvariant solutions.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsStefan Arnborg, Lars Ivansson
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540646825, 9783540646822
StatePublished - 1998
Event6th Scandinavian Workshop on Algorithm Theory, SWAT 1998 - Stockholm, Sweden
Duration: Jul 8 1998Jul 10 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th Scandinavian Workshop on Algorithm Theory, SWAT 1998

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Facility location with dynamic functions distance'. Together they form a unique fingerprint.

Cite this