On Minimizing the Number of ADMs in a General Topology Optical Network

摘要

Minimizing the number of electronic switches in optical networks is a main research topic in recent studies. In such networks we assign colors to a given set of lightpaths. Thus the lightpaths are partitioned into cycles and paths, and the switching cost is minimized when the number of paths is minimized. The problem of minimizing the switching cost is NP-hard. A basic approximation algorithm for this problem eliminates cycles of size at most l, and has a performance guarantee of OPT + 1/2(1 + ε)N, where OPT is the cost of an optimal solution, N is the number of lightpaths, and 0 ≤ ε ≤ 1/l+2, for any given odd l. We improve the analysis of this algorithm and prove that ε ≤ 1/(3/2)(l+2). This implies an improvement in the running time of the algorithm: for any ε, the exponent of the running time needed for the same approximation ratio is reduced by a factor of 3/2. We also show a lower bound of ε ≥ 1/2l+3. In addition, in our analysis we suggest a novel technique, including a new combinatorial lemma.