Geodesic
A Note on Spanning Trees for Network Location Problems
Yugoslav journal of operations research, Tome 8 (1998) no. 1, p. 129 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

A p-facility location problem on a network N consists of locating p new facilities on N such that some function of the distances from them to the vertices of N is minimized. We consider a class of such problems where the objective function is nondecreasing in distance. Median, center and centdian problems belong to this class. We prove that the optimal solutions on the network and on the corresponding spanning trees are equal. Since location problems on a tree network are easier to solve than on a general one, we propose a descent local search heuristic that optimally solves the problem on a spanning tree at each iteration.
Classification : 90B80 90C35 90C59
Keywords: Location, network, spanning trees, heuristic 
@article{YJOR_1998_8_1_a7,
     author = {Dionisio P\'erez-Brito and Nenad Mladenovi\'c and Jos\'e A. Moreno-P\'erez},
     title = {A {Note} on {Spanning} {Trees} for {Network} {Location} {Problems}},
     journal = {Yugoslav journal of operations research},
     pages = {129 },
     publisher = {mathdoc},
     volume = {8},
     number = {1},
     year = {1998},
     zbl = {0951.90032},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_1998_8_1_a7/}
}
TY  - JOUR
AU  - Dionisio Pérez-Brito
AU  - Nenad Mladenović
AU  - José A. Moreno-Pérez
TI  - A Note on Spanning Trees for Network Location Problems
JO  - Yugoslav journal of operations research
PY  - 1998
SP  - 129 
VL  - 8
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_1998_8_1_a7/
LA  - en
ID  - YJOR_1998_8_1_a7
ER  - 
%0 Journal Article
%A Dionisio Pérez-Brito
%A Nenad Mladenović
%A José A. Moreno-Pérez
%T A Note on Spanning Trees for Network Location Problems
%J Yugoslav journal of operations research
%D 1998
%P 129 
%V 8
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_1998_8_1_a7/
%G en
%F YJOR_1998_8_1_a7
Dionisio Pérez-Brito; Nenad Mladenović; José A. Moreno-Pérez. A Note on Spanning Trees for Network Location Problems. Yugoslav journal of operations research, Tome 8 (1998) no. 1, p. 129 . http://geodesic.mathdoc.fr/item/YJOR_1998_8_1_a7/