Preflow-push with excess scaling: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 13: Line 13:
# A sequence of iterations between two successive changes of <math>\Delta</math> is usually called a '''scaling phase'''.
# A sequence of iterations between two successive changes of <math>\Delta</math> is usually called a '''scaling phase'''.
# It is quite common in the literature to define an outer loop in which each iteration performs one scaling phase, and an inner loop performs the push-relabel steps. The break condition is usually <math>\Delta=0</math>. Clearly, when this condition is fulfilled, the [[Preflow-push#Abstract view|break condition]] of the [[Preflow-push|generic preflow-push algorithm]] is fulfilled as well.
# It is quite common in the literature to define an outer loop in which each iteration performs one scaling phase, and an inner loop performs the push-relabel steps. The break condition is usually <math>\Delta=0</math>. Clearly, when this condition is fulfilled, the [[Preflow-push#Abstract view|break condition]] of the [[Preflow-push|generic preflow-push algorithm]] is fulfilled as well.
== Induction basis ==
# All steps in the [[Preflow-push#Induction basis|induction basis]] of the [[Preflow-push|preflow push algorithm]].
# Set <math>\Delta:=2^L</math>, where <math>L:=\lceil\log_2U\rceil</math> and <math>U:=\max\{u(a)|a\in A\}</math>.
== Induction step ==
'''Abstract view:'''
A  the generic [[Preflow-push|preflow-push algorithm]] with the following modifications:
# Ignore all active nodes whose excess is smaller than <math>\Delta/2</math>. In particular, an iteration of the main loop is finished once no node has an excess of <math>\Delta/2</math> or more.
# Among the nodes with excess at least <math>\Delta/2</math>, choose one with minimum <math>d</math>-label.
# Do not push more than <math>\Delta-e_f(w)</math> units of flow over an arc <math>(v,w)</math>.
# At the end, set <math>\Delta:=\Delta/2</math>.
'''Proof:'''
obvious.
'''Definition:'''
The iterations of the following main loop are usually called the '''scaling phases'''.
== Correctness ==
Whenever an iteration is finished, no excess of <math>\Delta/2</math> or more is left at any node. When the break condition applies, no excess is left at all. Termination of the main loop follows from the following complexity considerations.


== Complexity ==
== Complexity ==

Revision as of 17:25, 10 November 2014

Abstract view

Algorithmic problem: max-flow problem (standard version)

Type of algorithm: a specialization of the generic preflow-push algorithm:

  1. An additional nonnegative integral number [math]\displaystyle{ \Delta/2 }[/math] is maintained, which is initialized so as to be at least as large as the largest upper bound of any arc (but not more than the next higher power of 2 for complexity reasons).
  2. In each iteration, an active node [math]\displaystyle{ v }[/math] may only be chosen if kit has large excess, that is, [math]\displaystyle{ e_f(v)\geq\Delta/2 }[/math].
  3. If there are active nodes but none with large excess, we reset [math]\displaystyle{ \Delta:=\Delta/2 }[/math] (integral division) until there is an active node with large excess.

Remarks:

  1. A sequence of iterations between two successive changes of [math]\displaystyle{ \Delta }[/math] is usually called a scaling phase.
  2. It is quite common in the literature to define an outer loop in which each iteration performs one scaling phase, and an inner loop performs the push-relabel steps. The break condition is usually [math]\displaystyle{ \Delta=0 }[/math]. Clearly, when this condition is fulfilled, the break condition of the generic preflow-push algorithm is fulfilled as well.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m+n^2\!\cdot\!\log U) }[/math]

Proof: In an operation of the main loop, let a large excess be at least [math]\displaystyle{ \Delta/2 }[/math] and a small excess be strictly less than [math]\displaystyle{ \Delta/2 }[/math].

Due to the selection rule for the next active node, every push step moves flow from a node with large excess to a node with small excess.

...

Now it suffices to show that there are [math]\displaystyle{ \mathcal{O}(n^2) }[/math] non-saturating push steps in every scaling phase.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Preflow-push_with_excess_scaling&oldid=2036"