𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A polynomial algorithm for thep-centdian problem on a tree

✍ Scribed by Tamir, Arie; P�rez-Brito, Dionisio; Moreno-P�rez, Jos� A.

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
108 KB
Volume
32
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A note on genetic algorithms for degree-
A note on genetic algorithms for degree-constrained spanning tree problems
✍ Zhou, Gengui; Gen, Mitsuo 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 2 views

The degree-constrained spanning tree problem is of high practical importance. Up to now, there are few effective algorithms to solve this problem because of its NP-hard complexity. In this paper, we present a new approach to solve this problem by using genetic algorithms and computational results to

A polynomial time algorithm for rectilin
A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves
✍ Brazil, M.; Thomas, D. A.; Weng, J. F. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP-complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectili

A tabu search algorithm for the Capacita
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
✍ Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 2 views

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynami

Algorithms for solving a spatial optimis
Algorithms for solving a spatial optimisation problem on a parallel computer
✍ George, Felicity; Radcliffe, Nicholas; Smith, Mark; Birkin, Mark; Clarke, Martin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 1 views

In a collaborative project between GMAP Ltd and EPCC, an existing heuristic optimisation scheme for strategic resource planning was parallelised to run on the data parallel Connection Machine CM-200. The parallel software was found to run over 2700 times faster than the original workstation software

The critical-item, upper bounds, and a b
The critical-item, upper bounds, and a branch-and-bound algorithm for the tree knapsack problem
✍ Shaw, Dong X.; Cho, Geon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB 👁 2 views

The tree knapsack problem (TKP) is a generalized 0-1 knapsack problem where all the items (nodes) are subjected to a partial ordering represented by a rooted tree. If a node is selected to be packed into the knapsack, then all the items on the path from the selected node to the root must also be pac