A polynomial algorithm for the p-centdian problem on a tree

A polynomial algorithm for the p-centdian problem on a tree

0.00 Avg rating0 Votes
Article ID: iaor20022154
Country: United States
Volume: 32
Issue: 4
Start Page Number: 255
End Page Number: 262
Publication Date: Dec 1998
Journal: Networks
Authors: , ,
Keywords: networks: path
Abstract:

The most common problems studied in network location theory are the p-median and the p-center models. The p-median problem on a network is concerned with the location of p points (medians) on the network, such that the total (weighted) distance of all the nodes to their respective nearest points is minimized. The p-center problem is concerned with the location of p-points (centers) on the network, such that the maximum (weighted) distance of all the nodes to their respective nearest points is minimized. To capture more real-world problems and obtain a good way to trade-off minisum (efficiency) and minimax (equity) approaches, Halpern introduced the centdian model, where the objective is to minimize a convex combination of the objective functions of the center and the median problems. In this paper, we studied the p-centdian problem on tree networks and present the first polynomial time algorithm for this problem.

Reviews

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