Inhalt des Dokuments
Preprint 02-2009
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Single-source k-splittable min-cost flows
- Authors
- Fernanda Salazar and Martin Skutella
- Publication
- Operations Research Letters, 2009, to appear.
- Classification
-
not available
- Keywords
-
Approximation Algorithm; Multi-Commodity Flow; Network Flow; Routing; Unsplittable Flow; k-Splittable Flow
- 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.
- Source
- Download as [PDF]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe