Geodesic
Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017 , Tome 23 (2019) no. 1, pp. 93-110.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We consider a single allocation hub-and-spoke network design problem which allocates each non-hub node to exactly one of the given hub nodes in order to minimize the total transportation cost. This paper deals with a cycle-star hub network design problem, in which the hubs are located in a cycle. This problem is essentially equivalent to a cycle-metric labeling problem. It is useful in the design of networks in telecommunications and airline transportation systems. We propose a $2(1-1/h)$-approximation algorithm, where $h$ denotes the number of hub nodes. Our algorithm solves a linear relaxation problem and employs a dependent rounding procedure. We analyze our algorithm by approximating a given cycle-metric matrix using a convex combination of Monge matrices.
DOI : 10.7155/jgaa.00485
Keywords: approximation algorithm, network design, metric labeling 
@article{JGAA_2019_23_1_a4,
     author = {Yuko Kuroki and Tomomi Matsui},
     title = {Approximation {Algorithm} for {Cycle-Star} {Hub} {Network} {Design} {Problems} and {Cycle-Metric} {Labeling} {Problems}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {93--110},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2019},
     doi = {10.7155/jgaa.00485},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00485/}
}
TY  - JOUR
AU  - Yuko Kuroki
AU  - Tomomi Matsui
TI  - Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 93
EP  - 110
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00485/
DO  - 10.7155/jgaa.00485
LA  - en
ID  - JGAA_2019_23_1_a4
ER  - 
%0 Journal Article
%A Yuko Kuroki
%A Tomomi Matsui
%T Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
%J Journal of Graph Algorithms and Applications
%D 2019
%P 93-110
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00485/
%R 10.7155/jgaa.00485
%G en
%F JGAA_2019_23_1_a4
Yuko Kuroki; Tomomi Matsui. Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 11th International Conference and  Workshops on Algorithms and Computation, WALCOM 2017
					, Tome 23 (2019) no. 1, pp. 93-110. doi : 10.7155/jgaa.00485. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00485/

Cité par Sources :