Treffer: Approximating circular arc colouring and bandwidth allocation in all-optical ring networks.

We present randomized approximation algorithms for the circular arc graph colouring problem and for the problem of bandwidth allocation in all-optical ring networks. We obtain a factor-of-(1+1/e+o(1)) randomized approximation algorithm for the arc colouring problem, an improvement over the best previously known performance ratio of 5/3. For the problem of allocating bandwidth in an all-optical WDM (wavelength division multiplexing) ring network, we present a factor-of-(1.5+1/2e+o(1)) randomized approximation algorithm, improving upon the best previously known performance ratio of 2. [ABSTRACT FROM AUTHOR]