Complexity and Approximability of k-Splittable Flows

dc.contributor.authorKoch, Ronald
dc.contributor.authorSpenke, Ines
dc.date.accessioned2021-12-17T10:06:20Z
dc.date.available2021-12-17T10:06:20Z
dc.date.issued2005
dc.description.abstractLet G=(V,E) be a graph with a source node s and a sink node t, |V| = n, |E|= m. For a given number k, the Maximum k-Splittable Flow Problem (MkSF) is to find an s,t-flow of maximum value with a flow decomposition using at most k paths. In the multicommodity case this problem generalizes disjoint paths problems and unsplittable flow problems. We provide a comprehensive overview of the complexity and approximability landscape of MkSF on directed and undirected graphs. We consider constant values of k and k depending on graph parameters. For arbitrary constant values of k, we prove that the problem is strongly NP-hard on directed and undirected graphs already for k=2. This extends a known NP-hardness result for directed graphs that could not be applied to undirected graphs. Furthermore, we show that MkSF cannot be approximated with a performance ratio better than 5/6. This is the first constant bound given for this value. For non constant values of k, the polynomially solvability was known before for all k >= m, but open for smaller k. We prove that MkSF is NP-hard for all k fulfilling 2 <= k <= m-n+1 (for n >= 3). For all other values of k the problem is shown to be polynomially solvable.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15553
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14326
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.othernetwork flowsen
dc.subject.otherk-splittable flowsen
dc.subject.othercomplexityen
dc.subject.otherapproximabilityen
dc.subject.others, t-flowen
dc.titleComplexity and Approximability of k-Splittable Flowsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2005, 29en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200090C60 Abstract computational complexity for mathematical programming problemsen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-029-2005.pdf
Size:
152.57 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-029-2005.ps.gz
Size:
151.8 KB
Format:
Unknown data format

Collections