Y.Y. Li, K.S. Leung, et al.
J Combin Optim
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.
Y.Y. Li, K.S. Leung, et al.
J Combin Optim
Peter Wendt
Electronic Imaging: Advanced Devices and Systems 1990
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
Fernando Martinez, Juntao Chen, et al.
AAAI 2025