An approximation algorithm for circular arc colouring

Abstract

We consider the problem of colouring a family of n arcs of a circle. This NP-complete problem, which occurs in routing and network design problems, is modelled as a 0-1 integer multicommodity flow problem. We present an algorithm that routes the commodities in the network by augmenting the network with some extra edges which correspond to extra colours. The algorithm, which relies on probabilistic techniques such as randomized rounding and path selection, is a randomized approximation algorithm which has an asymptotic performance ratio of 1 + 1/e (approximately 1.37) except when the minimum number of colours required is very small (O(In n)). This is an improvement over the best previously known result [7], which is a deterministic approximation algorithm with a performance ratio of 3/2. The substantial improvement is valuable, for instance in wavelength allocation strategies in communication networks where bandwidth is a precious resource.