Advertisement
Published in:
2017 | OriginalPaper | Chapter
Algorithms for the Ring Star Problem
Authors : Xujin Chen, Xiaodong Hu, Zhongzheng Tang, Chenhao Wang, Ying Zhang
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We address the Ring Star Problem (RSP) on a complete graph \(G=(V,E)\) whose edges are associated with both a nonnegative ring cost and a nonnegative assignment cost. The RSP is to locate a simple ring (cycle) R in G with the objective of minimizing the sum of two costs: the ring cost of (all edges in) R and the assignment cost for attaching nodes in \(V\setminus V(R)\) to their closest ring nodes (in R). We focus on the metric RSP with fixed edge-cost ratio, in which both ring cost function and assignment cost function defined on E satisfy triangle inequalities, and the ratios between the ring cost and assignment cost are the same value \(M\ge 1\) for all edges.
We show that the star structure is an optimal solution of the RSP when \(M\ge (|V|-1)/2\). This particularly implies a \(\sqrt{|V|-1}\)-approximation algorithm for the general RSP. Heuristics based on some natural strategies are proposed. Simulation results demonstrate that the proposed approximation and heuristic algorithms have very good practical performances. We also consider the capacitated RSP which puts an upper limit k on the number of leaf nodes that a ring node can serve. We present a \((10+6M/k)\)-approximation algorithm for the capacitated generalization.