On Minimizing the Numbers of ADMs-Better Bounds for an Algorithm with Preprocessing
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 ι and has a performance guarantee of OPT + 1/2N(1 + ε), where OPT is the cost of an optimal solution, N is the number of lightpaths and 0 ≤ ε ≤1/ι+2, for any given odd ι. Shalom improved the analysis of this algorithm and prove that 1/2ι+3 ≤ ε ≤ 1/3/2(ι+2). In this paper, we further reduce the gap between the lower bound and the upper bound of ε. We show that a better upper bound of ε by constructing a greater matching,i.e., ε≤ 1/5/3(ι+2).
Wavelength Assignment Wavelength Division Multiplexing(WDM) Optical Networks Add-Drop Multiplexer(ADM)
Su-xia Cui Ji-guo Yu Bao-xiang Cao
School of Computer Science, Qufu Normal University, Ri-zhao, Shandong, 276826
国际会议
The Seventh International Symposium(ISORA08)(第七届国际效力研究及其应用学术会议)
云南丽江
英文
219-230
2008-10-31（万方平台首次上网日期，不代表论文的发表时间）