Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017
DOI: 10.7155/jgaa.00485
Approximation Algorithm for CycleStar Hub Network Design Problems and CycleMetric Labeling Problems
Yuko Kuroki and
Tomomi Matsui
Vol. 23, no. 1, pp. 93110, 2019. Regular paper.
Abstract We consider a single allocation hubandspoke
network design problem
which allocates each nonhub node
to exactly one of the given hub nodes
in order to minimize the total transportation cost.
This paper deals with a cyclestar hub network design problem,
in which the hubs are located in a cycle. This problem is essentially equivalent
to a cyclemetric labeling problem.
It is useful in the design of networks in telecommunications
and airline transportation systems.
We propose a $2(11/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 cyclemetric matrix
using a convex combination of Monge matrices.

Submitted: August 2017.
Reviewed: May 2018.
Revised: June 2018.
Reviewed: July 2018.
Revised: August 2018.
Accepted: August 2018.
Final: August 2018.
Published: January 2019.
