Motion video analysis using planar parallax
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994
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.
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994
Andrew Skumanich
SPIE Optics Quebec 1993
Jianke Yang, Robin Walters, et al.
ICML 2023
M.B. Small, R.M. Potemski
Proceedings of SPIE 1989