Approximation Algorithm For Routing And Spectrum Assignment Problems

This paper studies the spectrum assignment(S A)problem in chain and ring network-s,which is a key network design and control problem in spectrum slice elastic optical path networks.The SA problem of several NP-hard cases,we design a approximation algo-rithm with theoretical performance guarantee.In the first chapter,we first introduce the basic concepts of network optimization scheduling problems and the definitions of approximation algorithms and computational complexity.Then introduce the related research on routing and spectrum assignment,and finally describe the structure of the whole paper.In the second chapter,the problem of spectrum assignment in the chain network structure is studied.The problem of spectrum assignment in chain network structure can be transformed into parallel machine scheduling problem.Based on the lower bound of the problem,using the combination idea,for the case of N=5,we propose an improved approximation algorithm with approximation ratio of 4/3(better than the algorithm with approximation ratio of 1.5 in the literature);In the case of N=6,we design an improved approximation algorithm with al approximate ratio of 4/3(also better than the algorithm with an approximation of 1.5 in the literature).Finally,for the general case,we also get the improved results.The third chapter mainly studies the routing and spectrum assignment of the ring net?work structure.Similarly,the problem of spectrum allocation in a ring network structure can also translate into parallel machine ordering problems.Based on the lower bound of the problem,using the combination idea,for the case of N=5,we propose an improved approximation algorithm with approximation ratio of 4/3(better than the algorithm with approximation ratio of 1.5 in the literature);For the case of N=6 and N=7,we design an improved approximation algorithm with an approximate ratio of 1.5(also better than the algorithm with an approximation of 2 in the literature).Finally,for the general case,we also get the improved results.The fourth chapter is a brief summary of the research content of this paper.