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 Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
Yuko Kuroki and
Tomomi Matsui
Vol. 23, no. 1, pp. 93-110, 2019. Regular paper.
Abstract 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.
|
Submitted: August 2017.
Reviewed: May 2018.
Revised: June 2018.
Reviewed: July 2018.
Revised: August 2018.
Accepted: August 2018.
Final: August 2018.
Published: January 2019.
|
Journal Supporters
|