کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420463 | 683942 | 2009 | 17 صفحه PDF | دانلود رایگان |
Minimizing the number of electronic switches in optical networks has been a main research topic in some recent studies. In such networks, we assign colors to a given set of lightpaths, and they are partitioned into unicolor cycles and paths; the switching cost is minimized when the number of paths is minimized. Most approximation and heuristic algorithms for this problem have a preprocessing stage, in which possible cycles are found. Among them, the basic algorithm eliminates cycles of size at most ll, and has a performance guarantee of OPT+12(1+ϵ)N, where OPTOPT is the cost of an optimal solution, NN is the number of lightpaths and 0≤ϵ≤1l+2, for any given odd ll. The time complexity of the algorithm is exponential in ll. We improve the analysis of this algorithm, by showing that ϵ≤132(l+2), which implies a reduction of the exponent in the time complexity. We also improve the lower bound by showing that ϵ≥12l+3. 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.
Journal: Discrete Applied Mathematics - Volume 157, Issue 12, 28 June 2009, Pages 2701–2717