Facility location with dynamic distance functions

Facility location problems have always been studied with the assumption tha t the edge lengths in the network are static and do not change over time. T he underlying network could be used to model a city street network for emer gency facility location/hospitals, or an electronic network for locating in formation centers. In any case, it is clear that due to traffic congestion the traversal time on links changes with time. Very often, we have estimate s as to how the edge lengths change over time, and our objective is to choo se a set of locations (vertices) as centers, such that at every lime instan t each vertex has a center close to it (clearly, the center close to a vert ex 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 l ocation for good time-invariant solutions.