Thumbnail Image

Single-source k-splittable min-cost flows

Salazar, Fernanda; Skutella, Martin

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

Motivated by a famous open question on the single-source unsplittable minimum cost flow problem, we present a new approximation result for the relaxation of the problem where, for a given number k, each commodity must be routed along at most k paths.