Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Single source unsplittable flows with arc-wise lower and upper bounds
Author(s): Morell, Sarah
Skutella, Martin
Type: Article
Abstract: In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from x by too much, i.e., ya≈xa for all arcs a. Twenty years ago, in a landmark paper, Dinitz et al. (Combinatorica 19:17–41, 1999) proved that there exists an unsplittable flow y such that ya≤xa+dmax for all arcs a, where dmax denotes the maximum demand value. Our first contribution is a considerably simpler one-page proof for this classical result, based upon an entirely new approach. Secondly, using a subtle variant of this approach, we obtain a new result: There is an unsplittable flow y such that ya≥xa−dmax for all arcs a. Finally, building upon an iterative rounding technique previously introduced by Kolliopoulos and Stein (SIAM J Comput 31:919–946, 2002) and Skutella (Math Program 91:493–514, 2002), we prove existence of an unsplittable flow that simultaneously satisfies the upper and lower bounds for the special case when demands are integer multiples of each other. For arbitrary demand values, we prove the weaker simultaneous bounds xa/2−dmax≤ya≤2xa+dmax for all arcs a.
Subject(s): network flow
unsplittable flow
flow augmentation
Issue Date: 1-Sep-2021
Date Available: 17-May-2022
Language Code: en
DDC Class: 510 Mathematik
Sponsor/Funder: TU Berlin, Open-Access-Mittel – 2021
Journal Title: Mathematical Programming
Publisher: Springer Nature
Volume: 192
Publisher DOI: 10.1007/s10107-021-01704-4
Page Start: 477
Page End: 496
EISSN: 1436-4646
ISSN: 0025-5610
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik » FG Kombinatorische Optimierung und Graphenalgorithmen
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 553.4 kB
DownloadShow Preview

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons