Preflow-push with excess scaling: Difference between revisions

Revision as of 15:01, 29 October 2014

Algorithmic problem: max-flow problem (standard version)

Type of algorithm: a variation of the generic preflow-push algorithm.

Invariant: Before and after each iteration:

All points of the invariant of the preflow-push algorithm.
There is a nonnegative, integral value [math]\displaystyle{ \Delta }[/math], and the excess [math]\displaystyle{ e_f(v) }[/math] of no active node [math]\displaystyle{ v }[/math] exceeds [math]\displaystyle{ \Delta }[/math].

Variant: [math]\displaystyle{ \Delta }[/math] is divided by two (integral division).

Break condition: [math]\displaystyle{ \Delta=0 }[/math].

All steps in the induction basis of the preflow push algorithm.
Set [math]\displaystyle{ \Delta:=2^L }[/math], where [math]\displaystyle{ L:=\lceil\log_2U\rceil }[/math] and [math]\displaystyle{ U:=\max\{u(a)|a\in A\} }[/math].

Abstract view: Run the preflow-push algorithm with two modifications:

Ignore all active nodes whose excess is smaller than [math]\displaystyle{ \Delta/2 }[/math].
Among the nodes with excess at least [math]\displaystyle{ \Delta/2 }[/math], choose one with minimum [math]\displaystyle{ d }[/math]-label.
Do not push more than [math]\displaystyle{ \Delta-e_f(w) }[/math] units of fow over an arc [math]\displaystyle{ (v,w) }[/math].

@@ Line 9: / Line 9: @@
 '''Invariant:'''
 Before and after each iteration:
-# The current flow is feasible.
+# All points of the invariant of the [[Preflow-pus|preflow-push algorithm]].
-# There is a nonnegative, integral value <math>\Delta</math>.
+# There is a nonnegative, integral value <math>\Delta</math>, and the excess <math>e_f(v)</math> of no active node <math>v</math> exceeds <math>\Delta</math>.
-# The excess <math>e_f(v)</math> of no active node <math>v</math> exceeds <math>\Delta</math>.
 '''Variant:'''