Single-source k-splittable min-cost flows

Abstract:

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. © 2009 Elsevier B.V. All rights reserved.

Año de publicación:

2009

Keywords:

• Network flow
• Approximation algorithm
• Unsplittable flow
• Multi-commodity flow
• k-splittable flow
• routing

Fuente:

scopus