Locating centers in dynamically changing network and related problems


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.