Preflow-push with excess scaling: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 5: | Line 5: | ||
'''Type of algorithm:''' | '''Type of algorithm:''' | ||
a variation of the [[Preflow-push|generic preflow-push algorithm]]. | |||
'''Invariant:''' | '''Invariant:''' | ||
| Line 11: | Line 11: | ||
# The current flow is feasible. | # The current flow is feasible. | ||
# There is a nonnegative, integral value <math>\Delta</math>. | # There is a nonnegative, integral value <math>\Delta</math>. | ||
# The excess of no node exceeds <math>\Delta</math>. | # The excess <math>e_f(v)</math> of no active node <math>v</math> exceeds <math>\Delta</math>. | ||
'''Variant:''' | '''Variant:''' | ||
| Line 23: | Line 23: | ||
# All steps in the [[Preflow-push#Induction basis|induction basis]] of the [[Preflow-push|preflow push algorithm]]. | # 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:=<math>\lceil\log_2U\rceil</math> and <math>U:=\max\{u(a)|a\in A\}</math>. | # Set <math>\Delta:=2^L</math>, where <math>L:=<math>\lceil\log_2U\rceil</math> and <math>U:=\max\{u(a)|a\in A\}</math>. | ||
== Induction step == | |||
'''Abstract view:''' | |||
Run the [[Preflow-push|preflow-push algorithm]] with two modifications: | |||
# Ignore all active nodes whose excess is smaller than <math>\Delta/2</math>. | |||
# Among the nodes with excess at least <math>\Delta/2</math>, choose one with minimum <math>d</math>-label. | |||
# Do not push more | |||
Revision as of 13:51, 29 October 2014
Abstract view
Algorithmic problem: max-flow problem (standard version)
Type of algorithm: a variation of the generic preflow-push algorithm.
Invariant: Before and after each iteration:
- The current flow is feasible.
- There is a nonnegative, integral value [math]\displaystyle{ \Delta }[/math].
- 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].
Induction basis
- All steps in the induction basis of the preflow push algorithm.
- Set [math]\displaystyle{ \Delta:=2^L }[/math], where [math]\displaystyle{ L:=\lt math\gt \lceil\log_2U\rceil }[/math] and [math]\displaystyle{ U:=\max\{u(a)|a\in A\} }[/math].
Induction step
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