Special Issue on Selected Papers from the 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017 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. Communicated by Md. Saidur Rahman, Hsu-Chun Yen, and Sheung-Hung Poon article (PDF) BibTeX