Single source unsplittable flows with arc-wise lower and upper bounds
研究在有向图中，给定一个可能可分拆的流，如何找到一条不可分拆流，使其每条弧上的流量与原始流偏差不超过最大需求值，并给出了更简单的证明和新的上下界结果。
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., $$y_a\approx x_a$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>y</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>≈</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>a</mml:mi> </mml:msub> </mml:mrow> </mml:math> 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 $$y_a\le x_a+d_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>y</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>d</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> for all arcs a , where $$d_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>d</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:math> 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 $$y_a\ge x_a-d_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>y</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>≥</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>-</mml:mo> <mml:msub> <mml:mi>d</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> 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 $$x_a/2-d_{\max }\le y_a\le 2x_a+d_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:msub> <mml:mi>d</mml:mi> <mml:mo>max</mml:mo> </mml:msub> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>y</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>≤</mml:mo> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>a</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>d</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> for all arcs a .