**Locating centers in dynamically changing network and related problems**

## Abstract

In a dynamically changing network the costs or distances between
locations are changing in each discrete time period. We consider
the location of emergency facilities that must minimize the
maximum distance to any customer on the network across *all*
time periods. We call the problem of locating p centers over k
underlying networks corresponding to k periods the
k-*Network* p-*Center* problem. The problem is considered when in each period the
network satisfies the
triangle inequality.

In this paper we provide a polynomial time 3-approximation algorithm for
k-*Network* p-*Center* for the case k = 2.

We discuss generalizations inspired by this problem to other
optimization problems with
multiple underlying networks and the objective of finding a single
solution that varies as little as possible from the optimum for
each network.
The additional combinatorial problems discussed include: sorting;
perfect matching; shortest path; minimum spanning tree; and minimum
cut. All are shown to be NP-hard for k 2.

## Download Information

Click on the following title to view and download the paper in PostScript format.

*Locating centers in dynamically changing network and related problems (14 pages, 202 KB)* ,
- Dorit S. Hochbaum and Anu Pathria. Manuscript (December 1996). To appear in
*Location Science*.

`dorit@hochbaum.ieor.berkeley.edu`
7/30/98