Successive shortest paths: Difference between revisions

Latest revision as of 10:08, 6 May 2015

Abstract view

Algorithmic problem: Min-cost flow problem

Type of algorithm: loop

Definition:

For a node [math]\displaystyle{ v\in V }[/math], let [math]\displaystyle{ \delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v) }[/math].
The imbalance of a node [math]\displaystyle{ v\in V }[/math] is defined as [math]\displaystyle{ I_f(v):=\delta f(v)-b(v) }[/math].
The imbalance of a node [math]\displaystyle{ v\in V }[/math] is underestimating if [math]\displaystyle{ 0\leq\delta f(v)\leq b(v) }[/math] or [math]\displaystyle{ 0\geq\delta f(v)\geq b(v) }[/math].
The total imbalance of [math]\displaystyle{ f }[/math] is defined as [math]\displaystyle{ \sum_{v\in V}|I_f(v)| }[/math].

Invariant:

The capacity constraints are fulfilled, that is, [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
There is no negative cycle in the residual network of [math]\displaystyle{ f }[/math].
The imbalance of every node is underestimating.

Variant: The total imbalance strictly decreases.

Break condition: The imbalances of all nodes are zero or there is no augmenting path from some node [math]\displaystyle{ v\in V }[/math] with [math]\displaystyle{ I_f(v)\lt 0 }[/math] to any node [math]\displaystyle{ w }[/math] with [math]\displaystyle{ I_f(w)\gt 0 }[/math].

Induction basis

Abstract view: Start with the zero flow.

Proof: Obvious.

Induction step

Choose some node [math]\displaystyle{ s }[/math] with [math]\displaystyle{ I_f(s)\lt 0 }[/math].
Find a shortest [math]\displaystyle{ (s,t) }[/math]-path [math]\displaystyle{ p }[/math] to some node [math]\displaystyle{ t }[/math] with [math]\displaystyle{ I_f(t)\gt 0 }[/math].
If there is none, terminate the algorithm.
Increase the flow on all arcs of [math]\displaystyle{ p }[/math] by the minimum of the following three values: [math]\displaystyle{ |I_f(s)| }[/math], [math]\displaystyle{ I_f(t)\gt 0 }[/math], and the minimal residual capacity taken over all arcs on [math]\displaystyle{ p }[/math].

Remark: Since cost values may be negative in the residual network, step 2 requires an algorithm that copes with negative arc lengths. In particular, efficient algorithms such as Dijkstra's are not an option. However, a variant of the algorithm works on a nonnegative variation of the cost values, which allows efficient algorithms.

Proof: The variant follows from the fact that the amount by which the flow is increased in step 3 is strictly positive. The first and third points of the invariant result from the choice of this amount as the minimum of the imbalances of the end nodes and all residual capacities. Thus, it remains to show point 2 of the invariant.

By induction hypothesis, there were no negative cycles immediately before the iteration. So, any negative cycle [math]\displaystyle{ C }[/math] must have been created by the flow augmentation along [math]\displaystyle{ p }[/math]. Let [math]\displaystyle{ p_1,\ldots,p_k }[/math] denote the inclusion-maximal subpaths of [math]\displaystyle{ C }[/math] whose internal nodes do not belong to [math]\displaystyle{ p }[/math]. In other words, each [math]\displaystyle{ p_i }[/math] starts and ends on [math]\displaystyle{ p }[/math] but does not share any further node with [math]\displaystyle{ p }[/math]. Now, for [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math], let [math]\displaystyle{ p'_i }[/math] denote

the subpath of [math]\displaystyle{ p }[/math] from the start node of [math]\displaystyle{ p_i }[/math] to the end node of [math]\displaystyle{ p_i }[/math], if the start node of [math]\displaystyle{ p_i }[/math] appears on [math]\displaystyle{ p }[/math] before its end node;
the subpath of the transpose of [math]\displaystyle{ p }[/math] from the start node of [math]\displaystyle{ p_i }[/math] to the end node of [math]\displaystyle{ p_i }[/math], if the end node of [math]\displaystyle{ p_i }[/math] appears on [math]\displaystyle{ p }[/math] before the start node of [math]\displaystyle{ p_i }[/math].

Further, let [math]\displaystyle{ C' }[/math] be the cycle that results from [math]\displaystyle{ C }[/math] when each subpath [math]\displaystyle{ p_i }[/math] is replaced by the corresponding subpath [math]\displaystyle{ p'_i }[/math] of [math]\displaystyle{ p }[/math] (in the first case) or of the transpose of [math]\displaystyle{ p }[/math] (in the second case). In general, this cycle is extremely non-simple. It contains each arc of [math]\displaystyle{ p }[/math] as often as its opposite arc. Therefore, the total cost of [math]\displaystyle{ C' }[/math] ist zero. Now it suffices to show that the total cost of [math]\displaystyle{ C }[/math] is not smaller than the total cost of [math]\displaystyle{ C' }[/math]. More specifically, for each [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math], we will show that the cost of [math]\displaystyle{ p_i }[/math] is not smaller than the cost of [math]\displaystyle{ p'_i }[/math]. Note that all arcs on all subpaths [math]\displaystyle{ p_i }[/math] are in the residual network immediately before and immediately after the current iteration (with positive residual capacity, by definition). We apply the case distinction in the definition of [math]\displaystyle{ p'_i }[/math] above.

For a path [math]\displaystyle{ p_i }[/math] of the first type, the fact that [math]\displaystyle{ p }[/math] is a shortest path implies that [math]\displaystyle{ p_i }[/math] is a shortest path from its start node to its end node in the residual network immediately before the current iteration. Therefore, [math]\displaystyle{ p'_i }[/math] is not shorter than [math]\displaystyle{ p_i }[/math].
For a path [math]\displaystyle{ p_i }[/math] of the second type, let [math]\displaystyle{ p''_i }[/math] denote the transpose of [math]\displaystyle{ p'_i }[/math]. In particular, [math]\displaystyle{ p''_i }[/math] is a subpath of [math]\displaystyle{ p }[/math]. Note that [math]\displaystyle{ p_i }[/math] and [math]\displaystyle{ p''_i }[/math] form a cycle, and that this cycle was augmenting immediately before the current iteration. By induction hypothesis, this cycle is not negative, [math]\displaystyle{ c(p_i)+c(p''_i)\geq 0 }[/math]. The claim now follows from [math]\displaystyle{ c(p'_i)=-c(p''_i) }[/math].

Correctness

The proof of the induction step shows that the invariant is fulfilled on termination. If no path is found, the instance is obviously infeasible. On the other hand, if all imbalances are removed, the resulting flow is feasible. Due to the second point of the invariant, it is also minimum (cf. here).

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(B\cdot T) }[/math], where [math]\displaystyle{ B=\sum_{v\in V}|b(v)| }[/math], and [math]\displaystyle{ T }[/math] is the asymptotic complexity of the shortest-path algorithm.

Proof: Obviously, the number of iterations is in [math]\displaystyle{ \mathcal{O}(B) }[/math]. The complexity of an iteration is dominated by the shortest-path computation.

@@ Line 1: / Line 1: @@
 == Abstract view ==
+'''Algorithmic problem:''' [[Min-cost flow problem]]
+'''Type of algorithm:''' loop
 '''Definition:'''
-# For a node <math>v\in V</math>, let <math>\Delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)</math>.
+# For a node <math>v\in V</math>, let <math>\delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)</math>.
-# The '''imbalance''' of a node <math>v\in V</math> is defined as <math>I_f(v):=\Delta f(v)-b(v)</math>.
+# The '''imbalance''' of a node <math>v\in V</math> is defined as <math>I_f(v):=\delta f(v)-b(v)</math>.
-# The imbalance of a node <math>v\in V</math> is '''underestimating''' if <math>0\leq \Delta f(v)\leq b(v)</math> or <math>0\geq\Delta f(v)\geq b(v)</math>.
+# The imbalance of a node <math>v\in V</math> is '''underestimating''' if <math>0\leq\delta f(v)\leq b(v)</math> or <math>0\geq\delta f(v)\geq b(v)</math>.
-# The '''total imbalance''' of <math>f</math> is the defined as <math>\sum_{v\in V}|I_f(v)|</math>.
+# The '''total imbalance''' of <math>f</math> is defined as <math>\sum_{v\in V}|I_f(v)|</math>.
 '''Invariant:'''
@@ Line 16: / Line 20: @@
 '''Break condition:'''
-The imbalances of all nodes are zero.
+The imbalances of all nodes are zero or there is no augmenting path from some node <math>v\in V</math> with <math>I_f(v)<0</math> to any node <math>w</math> with <math>I_f(w)>0</math>.
 == Induction basis ==
@@ Line 28: / Line 32: @@
 == Induction step ==
-# In the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>, find a shortest path <math>p</math> from the set of nodes <math>v\in V</math> with <math>I_f(v)<0</math> to the set of nodes <math>w\in V</math> with <math>I_f(v)>0</math>.
+# Choose some node <math>s</math> with <math>I_f(s)<0</math>.
-# Let <math>v_0</math> be the node where <math>p</math> actually starts and <math>w_0</math> the node where <math>p</math> actually ends.
+# Find a shortest <math>(s,t)</math>-path <math>p</math> to some node <math>t</math> with <math>I_f(t)>0</math>.
-# Increase the flow on all arcs of <math>p</math> by the minimum of <math>|I_f(v_0)|</math>, of <math>I_f(w_0)>0</math>, and of the [[Basic flow definitions#Residual network|residual capacities]] of all arcs on <math>p</math>.
+# If there is none, terminate the algorithm.
+# Increase the flow on all arcs of <math>p</math> by the minimum of the following three values: <math>|I_f(s)|</math>, <math>I_f(t)>0</math>, and the minimal [[Basic flow definitions#Residual network|residual capacity]] taken over all arcs on <math>p</math>.
-== Correctness ==
+'''Remark:'''
+Since cost values may be negative in the [[Basic flow definitions#Residual network|residual network]], step 2 requires an algorithm that copes with negative arc lengths. In particular, efficient algorithms such as [[Dijkstra|Dijkstra's]] are not an option. However, a [[Successive shortest paths with reduced costs|variant]] of the algorithm works on a nonnegative variation of the cost values, which allows efficient algorithms.
-The variant follows from the fact that the amount by which the flow is increased in step 3 is strictly positive. The first and third points of the invariant result from the choice of this amount as the minimum of imbalances and residual capacities. Thus, it remains to show point 2 of the invariant.
+'''Proof:'''
+The variant follows from the fact that the amount by which the flow is increased in step 3 is strictly positive. The first and third points of the invariant result from the choice of this amount as the minimum of the imbalances of the end nodes and all residual capacities. Thus, it remains to show point 2 of the invariant.
-By induction hypothesis, there were nonegative cycles immediately before the iteration. So, any negative cycle <math>C</math> must have been introduced by the flow augmentation along <math>p</math>. Such a cycle must contain at least one arc <math>(v,w)</math> on <math>p</math> such that the residual capacity <math>w\rightarrow v</math> was zero immediately before the current iteration (and is positive afterwards, of course). Suppose for a contradiction that a negative cycle <math>C</math> has been introduced. For some <math>k>0</math>, let <math>(v_1,w_1),\ldots,(v_k,w_k)</math> denote, in this (cyclic) order, the arcs on <math>p</math> such that, for each <math>k\in\{1,\ldots,,k\}</math>, <math>(w_i,v_i)</math> belongs to <math>C</math> and the residual capacity of <math>(w_i,v_i)</math> was zero immediately before the current iteration.
+By induction hypothesis, there were no negative cycles immediately before the iteration. So, any negative cycle <math>C</math> must have been created by the flow augmentation along <math>p</math>. Let <math>p_1,\ldots,p_k</math> denote the [[Sets and sequences#Maximal and minimal sets|inclusion-maximal]] subpaths of <math>C</math> whose [[Basic graph definitions#Paths|internal nodes]]  do not belong to <math>p</math>. In other words, each <math>p_i</math> starts and ends on <math>p</math> but does not share any further node with <math>p</math>. Now, for <math>i\in\{1,\ldots,k\}</math>, let <math>p'_i</math> denote
+# the subpath of <math>p</math> from the start node of <math>p_i</math> to the end node of <math>p_i</math>, if the start node of <math>p_i</math> appears on <math>p</math> before its end node;
+# the subpath of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> from the start node of <math>p_i</math> to the end node of <math>p_i</math>, if the end node of <math>p_i</math> appears on <math>p</math> before the start node of <math>p_i</math>.
+Further, let <math>C'</math> be the cycle that results from <math>C</math> when each subpath <math>p_i</math> is replaced by the corresponding subpath <math>p'_i</math> of <math>p</math> (in the first case) or of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> (in the second case). In general, this cycle is extremely non-simple. It contains each arc of <math>p</math> as often as its opposite arc. Therefore, the total cost of <math>C'</math> ist zero. Now it suffices to show that the total cost of <math>C</math> is not smaller than the total cost of <math>C'</math>. More specifically, for each <math>i\in\{1,\ldots,k\}</math>, we will show that the cost of <math>p_i</math> is not smaller than the cost of <math>p'_i</math>. Note that all arcs on all subpaths <math>p_i</math> are in the residual network immediately before and immediately after the current iteration (with positive residual capacity, by definition). We apply the case distinction in the definition of <math>p'_i</math> above.
+# For a path <math>p_i</math> of the first type, the fact that <math>p</math> is a shortest path implies that <math>p_i</math> is a shortest path from its start node to its end node in the residual network immediately before the current iteration. Therefore, <math>p'_i</math> is not shorter than <math>p_i</math>.
+# For a path <math>p_i</math> of the second type, let <math>p''_i</math> denote the transpose of <math>p'_i</math>. In particular, <math>p''_i</math> is a subpath of <math>p</math>. Note that <math>p_i</math> and <math>p''_i</math> form a cycle, and that this cycle was augmenting immediately before the current iteration. By induction hypothesis, this cycle is not negative, <math>c(p_i)+c(p''_i)\geq 0</math>. The claim now follows from <math>c(p'_i)=-c(p''_i)</math>.
+== Correctness ==
-Let <math>p_1,\ldots,p_k</math> denote the maximal subpaths of <math>p</math> whose [[Basic graph definitions#Paths|internal nodes]]  do not belong to <math>p</math>. In other words, each <math>p_i</math> starts and ends on <math>p</math> but does not share any further node with <math>p</math>. All arcs no all of these subpaths are in the residual network immediately before and immediately after the current iteration. For <math>i\in\{1,\ldots,k\}</math>, let <math>p'</math> denote
+The proof of the induction step shows that the invariant is fulfilled on termination. If no path is found, the instance is obviously infeasible. On the other hand, if all imbalances are removed, the resulting flow is feasible. Due to the second point of the invariant, it is also minimum (cf. [[Negative cycle-canceling#Correctness|here]]).
-# the corresponding subpath of <math>p</math> if the start node of <math>p_i</math> appears on <math>p</math> before its end node;
-# the corresponding subpath of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> if the end node of <math>p_i</math> appears on <math>p</math> before its start node.
+== Complexity ==
-Let <math>C'</math> be the cycle that results from <math>C</math> when each subpath <math>p_i</math> of the first type is replaced by the corresponding subpath <math>p'_i</math> of <math>p</math>. Obviously, <math>C'</math> is augmenting immediately before the current iteration.
+'''Statement:'''
+The asymptotic complexity is in <math>\mathcal{O}(B\cdot T)</math>, where <math>B=\sum_{v\in V}|b(v)|</math>, and <math>T</math> is the asymptotic complexity of the shortest-path algorithm.
-Since <math>p</math> is shortest, each <math>p_i</math> of the first type is at least as long as the corresponding <math>p'_i</math> (recall that each <math>p_i</math> was augmenting when <math>p</math> was found).
+'''Proof:'''
+Obviously, the number of iterations is in <math>\mathcal{O}(B)</math>. The complexity of an iteration is dominated by the shortest-path computation.

Successive shortest paths: Difference between revisions

Latest revision as of 10:08, 6 May 2015

Contents

Abstract view

Induction basis

Induction step

Correctness

Complexity

Navigation menu

Successive shortest paths: Difference between revisions

Latest revision as of 10:08, 6 May 2015

Abstract view

Induction basis

Induction step

Correctness

Complexity

Navigation menu

Search