Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Approximation and complexity of k-splittable flows
Author(s): Koch, Ronald
Skutella, Martin
Spenke, Ines
Type: Research Paper
Abstract: Given a graph with a source and a sink node, the maximum k-splittable flow (MkSF) problem is to find a flow of maximum value with a flow decomposition using at most k paths. In the more general context of multicommodity flows, this NP-hard problem has been introduced by Baier, Koehler, and Skutella. It generalizes disjoint paths problems and unsplittable flows. A particularly interesting aspect of this problem is that its solution requires both packing and routing strategies. The total flow has to be divided into k packets which then have to be routed along certain paths of the given graph. The main contributions of this paper are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal MkSF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we canguarantee that, for any fixed ǫ >0, the computed set of alternatives contains a packing used by a (1−ǫ)–approximate solution. The latter result is based on the observation that (1−ǫ)–approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the MkSF problem can be solved in polynomial time on graphs of bounded tree width. If k is part of the input, this problem is still N P–hard and we present a polynomial time approximation scheme for it. (iii) Finally, we provide a comprehensive overview of the complexity and approximability landscape of MkSF for different values of k.
Subject(s): k-splittable flows
Issue Date: 2004
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2004, 19
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 174.02 kB
DownloadShow Preview
Format: Unknown | Size: 171.66 kB
Format: Postscript | Size: 387.46 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.