Technical Report CS-2006-14

TR#:CS-2006-14
Class:CS
Title: On Minimizing the Number of ADMs in a General Topology Optical Network
Authors: Michele Flammini, Mordechai Shalom, and Shmuel Zaks
PDFCS-2006-14.pdf
Abstract: 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, and approximation and heuristic algorithms have been suggested for it. Due to the structure of the solution, all of these approaches have a preprocessing stage, in which they first find possible cycles. The basic algorithm eliminates cycles of size at most $l$, and is known to have a performance guarantee of $OPT+\frac{1}{2}(1+\epsilon)N$, where $OPT$ is the cost of an optimal solution, $N$ is the number of lightpaths and $0 \leq \epsilon \leq \frac{1}{l+2}$, for any given odd $l$. The time complexity of the algorithm is exponential in $l$. We improve the analysis of this algorithm and prove a performance bound with $\epsilon \leq \frac{1}{\frac{3}{2}(l+2)}$. This result implies an improvement in the upper bound for the the running time of the algorithm: for any given $\epsilon >0$, the exponent of the running time needed to guarantee the approximation ratio $\frac{3+\epsilon}{2}$ is reduced by a factor of $3/2$. We present a family of instances for which $\epsilon \geq \frac{1}{2l+3}$, thus further closing the gap between these upper and lower bounds. The results shed more light on the structure of this basic algorithm. In addition, in our analysis we suggest a novel technique - including a new combinatorial lemma - to deal with this problem.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/CS/CS-2006-14), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2006
To the main CS technical reports page

Computer science department, Technion
admin