  We consider a single allocation hub-and-spoke network design problem which
allocates each non-hub node to exactly one of given hub nodes so as to minimize
the total transportation cost. This paper deals with a case in which the hubs
are located in a cycle, which is called a cycle-star hub network design
problem. The problem is essentially equivalent to a cycle-metric labeling
problem. The problem 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 by a convex
combination of Monge matrices.
