On Ring Grooming in optical networks

An instance I of Ring Grooming consists of m sets A 1,A 2,…, A m from the universe {0, 1,…, n − 1} and an integer g ≥ 2. The unrestricted variant of Ring Grooming, referred to as Unrestricted Ring Grooming, seeks a partition {P 1 , P 2, …,P k } of {1, 2, …, m} such that $$ \vert P_{i} \vert \leq g$$ for each 1 ≤ i ≤ k and $$ \sum _{i=1}^{k}\vert \bigcup_{r\in P_{i}}A_{r}\vert $$ is minimized. The restricted variant of Ring Grooming, referred to as Restricted Ring Grooming, seeks a partition $$\{ P_{1},P_{2},\ldots,P_{\lceil \frac{m}{g}\rceil}\}$$ of {1,2,…,m} such that | P i | ≤ g for each $$1\leq i\leq\lceil \frac {m}{g}\rceil $$ and $$ \sum_{i=1}^{k}\vert \bigcup_{r\in P_{i}} A_{r}\vert $$ is minimized. If g = 2, we provide an optimal polynomial-time algorithm for both variants. If g > 2, we prove that both both variants are NP-hard even with fixed g. When g is a power of two, we propose an approximation algorithm called iterative matching. Its approximation ratio is exactly 1.5 when g = 4, at most 2.5 when g = 8, and at most $$\frac{g}{2}$$ in general while it is conjectured to be at most $$\frac{g}{4}+\frac{1}{2}$$ . The iterative matching algorithm is also extended for Unrestricted Ring Grooming with arbitrary g, and a loose upper bound on its approximation ratio is $$\lceil \frac{g}{2}\rceil $$ . In addition, set-cover based approximation algorithms have been proposed for both Unrestricted Ring Grooming and Restricted Ring Grooming. They have approximation ratios of at most 1 + log g, but running time in polynomial of m g .