Facility Location with Dynamic Distance Functions
Facility Location with Dynamic Distance Functions
Files
Publication or External Link
Date
1998-10-15
Authors
Bhatia, Randeep
Guha, Sudipto
Khuller, Samir
Sussmann, Yoram J.
Advisor
Citation
DRUM DOI
Abstract
Facility location problems have always been studied with the
assumption that the edge lengths in the network are {\em 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 {\em changes} with time. Very often, we have some 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 {\em
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.
(Also cross-references as UMIACS-TR-97-70)