Premium
A polynomial algorithm for the p ‐centdian problem on a tree
Author(s) -
Tamir Arie,
PérezBrito Dionisio,
MorenoPérez José A.
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199812)32:4<255::aid-net2>3.0.co;2-o
Subject(s) - minimax , mathematics , tree network , center (category theory) , median , time complexity , combinatorics , algorithm , tree (set theory) , regular polygon , facility location problem , mathematical optimization , computer science , chemistry , geometry , crystallography
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. © 1998 John Wiley & Sons, Inc. Networks 32:255–262, 1998