Maximum k-Splittable Flows
| dc.contributor.author | Koch, Ronald | |
| dc.contributor.author | Skutella, Martin | |
| dc.contributor.author | Spenke, Ines | |
| dc.date.accessioned | 2021-12-17T10:06:19Z | |
| dc.date.available | 2021-12-17T10:06:19Z | |
| dc.date.issued | 2005 | |
| dc.description.abstract | Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (MkSF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values on these paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Our main contributions 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 can guarantee that, for any fixed epsilon>0, the computed set of alternatives contains a packing used by a (1-epsilon)-approximate solution. The latter result is based on the observation that (1-epsilon)-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 treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15552 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14325 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | network flows | en |
| dc.subject.other | k-splittable flows | en |
| dc.subject.other | approximation algorithms | en |
| dc.subject.other | PTAS | en |
| dc.subject.other | bounded treewidth | en |
| dc.title | Maximum k-Splittable Flows | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2005, 30 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
| tub.subject.msc2000 | 90C59 Approximation methods and heuristics | en |