Facility Location with Dynamic Distance Functions

TitleFacility Location with Dynamic Distance Functions
Publication TypeJournal Articles
Year of Publication1998
AuthorsKhuller S, Sussmann YJ, Bhatia R, Guha S
JournalJournal of Combinatorial Optimization
Pagination199 - 217
Date Published1998///

Facility location problems have always been studied with theassumption that the edge lengths in the network are static anddo not change over time. The underlying network could be used to model a city street networkfor emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to trafficcongestion 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) ascenters, 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 forthe K-center problem under this model. This is the first comprehensive study regarding approximation algorithmsfor facility location for good time-invariant solutions.