Facility Location with Dynamic Distance Functions

Loading...
Thumbnail Image

Files

CS-TR-3834.ps (247.27 KB)
No. of downloads: 163
CS-TR-3834.pdf (272 KB)
No. of downloads: 838

Publication or External Link

Date

1998-10-15

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)

Notes

Rights