Locating centers in a dynamically changing network, and related problems

Locating centers in a dynamically changing network, and related problems

0.00 Avg rating0 Votes
Article ID: iaor2000687
Country: United Kingdom
Volume: 6
Issue: 1/4
Start Page Number: 243
End Page Number: 256
Publication Date: May 1998
Journal: Location Science
Authors: ,
Keywords: networks
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.

Reviews

Required fields are marked *. Your email address will not be published.