ORIE Colloquium on 4/29/2014 - Martin Skutella: An Improved Additive Approximation for the Ring Loading Problem

Tuesday, April 29, 2014 at 4:15pm Frank H. T. Rhodes Hall, 253 ORIE Colloquium: Martin Skutella (TU Berlin) - An improved additive approximation for the ring loading problem The ring loading problem refers to the unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the ring loading problem can be turned into an unsplittable solution while increasing the flow value on any edge of the ring by no more than 1.4 times the maximum demand value d_max. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998) who obtained a slightly larger bound of 1.5 times d_max.