direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 739-2002

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

On the k-splittable Flow Problem
primary: 90C27 Combinatorial optimization
secondary: 90B10 Network models, deterministic
90C35 Programming involving graphs or networks
05C38 Paths and cycles
05C85 Graph algorithms
90C59 Approximation methods and heuristics
68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity
Approximation algorithms, graph algorithms, network flow, routing
In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for delivering each commodity; it is thus feasible to spread the flow over a large number of different paths. Motivated by routing problems arising in real-life applications, such as, e.g., telecommunication, unsplittable flows have moved into the focus of research. Here, the demand of each commodity may not be split but has to be sent along a single path.
In this paper, a generalization of this problem is studied. In the considered flow model, a commodity can be split into a bounded number of chunks which can then be routed on different paths. In contrast to classical (splittable) flows and unsplittable flows, already the single-commodity case of this problem is NP-hard and even hard to approximate. We present approximation algorithms for the single- and multi-commodity case and point out strong connections to unsplittable flows. Moreover, results on the hardness of approximation are presented. It particular, we show that some of our approximation results are in fact best possible, unless P=NP.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe