Preflow-push with excess scaling: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(24 intermediate revisions by the same user not shown)
Line 4: Line 4:
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]
[[Max-Flow Problems#Standard version|max-flow problem (standard version)]]


'''Type of algorithm:'''
This is a specialization and slight modification of the [[Preflow-push|generic preflow-push algorithm]]:
a specialization of the [[Preflow-push|generic preflow-push algorithm]]:
# An additional nonnegative integral number <math>\Delta</math> is maintained, which is initialized so as to be at least as large as the largest value <math>e_f</math> (but not more than the next higher power of 2 for complexity reasons, cf. [[#Complexity|here]]).
# An additional nonnegative integral number <math>\Delta</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).
# In each iteration, an active node <math>v</math> may only be chosen if it has '''large [[Basic flow definitions#Preflow|excess]]''', that is, <math>e_f(v)\geq\Delta/2</math>.
# In each iteration, an active node <math>v</math> may only be chosen if it has '''large [[Basic flow definitions#Preflow|excess]]''', that is, <math>e_f(v)\geq\Delta/2</math>.
# Among all active nodes with large excess, we choose one with minimum <math>d</math>-label.
# Among all active nodes with large excess, we choose one with minimum <math>d</math>-label.
# If there are active nodes but none with large excess, we do ''not'' apply a regular iteration but reset <math>\Delta:=\Delta/2</math> (integral division) until there is an active node with large excess.
# The flow value pushed over an arc <math>(v,w)</math> from <math>v</math> to <math>w</math> must be small enough so the excess of <math>w</math> does not exceed <math>\Delta</math> afterwards. In other words, the flow value to be pushed over <math>(v,w)</math> is ''not'' the minimum of <math>v</math>'s excess and the residual capacity of <math>(v,w)</math> as in the generic preflow-push algorithm; here it is the minimum of these two values ''and'' a third value, <math>\Delta-e_f(w)</math>, where <math>f</math> denotes the current preflow immediately before this push operation.
# If there are active nodes but none with large excess, we do ''not'' apply a push or relabel operation but reset <math>\Delta:=\Delta/2</math> (integral division) repeatedly until there is an active node with large excess.


'''Invariant:'''
'''Invariant:'''
# All invariants of the [[Preflow-push|generic pre flow-push algorithm]].
# All invariants of the [[Preflow-push|generic pre-flow push algorithm]].
# At any time, it is <math>e_f(v)\leq\Delta</math> for every node <math>v\in V\setminus\{s,t\}</math>.
# At any time, it is <math>e_f(v)\leq\Delta</math> for every node <math>v\in V\setminus\{s,t\}</math>.


'''Variant:'''
'''Variant:'''
The variant of the [[Preflow-push|generic pre flow-push algorithm]] is extended by a fourth option:  The value of <math>\Delta</math> is reduced to <math>\Delta/2</math>.
The variant of the [[Preflow-push|generic pre-flow push algorithm]] is extended by a fourth option:  The value of <math>\Delta</math> is reduced to <math>\Delta/2</math>.


'''Remarks:'''
'''Remarks:'''
Line 22: Line 22:
# 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.


== Implementation of point 3 ==
== Implementation of point 3 of the abstract algorithm ==


All active nodes with large excess are stored in an array of [[Sets and sequences|sets]] of nodes. The list at index <math>k</math> contains all active nodes <math>v\in V\setminus\{s,t\}</math> with large excess such that <math>d(v)=k</math>. This array is computed from scratch in the initialization and after every change of <math>\Delta</math>. A '''current array index''' is maintained, which is not larger than the index of any non-empty node set in the array. Whenever a node is to be chosen, the current array index is increased as long as the list at the current array index is empty. A push step may result in a new active node with large excess. However, this node has to be inserted at the index immediately before the current array index, so the current array index is never decreased by more than one.
All active nodes with large excess are stored in an array of [[Sets and sequences|sets]] of nodes. The list at index <math>k</math> contains all active nodes <math>v\in V\setminus\{s,t\}</math> with large excess and <math>d(v)=k</math>. This array is computed from scratch in the initialization and after every reduction of <math>\Delta</math>. A '''current array index''' is maintained, which is not larger than the index of any non-empty node set in the array. Whenever a node is to be chosen, the current array index is increased as long as the list at the current array index is empty. A push step may result in a new active node with large excess. However, this node has to be inserted at the index immediately before the current array index, so the current array index is never decreased by more than one unit at a time.


== Complexity ==
== Complexity ==
Line 32: Line 32:


'''Proof:'''
'''Proof:'''
The [[Preflow-push#Complexity|complexity considerations]] for the [[Preflow-push|generic preflow-push algorithm]] yield <math>\mathcal{O}(n^2)</math> relabel steps, <math>\mathcal{O}(n\!\cdot\!m)</math> saturating push steps, and <math>\mathcal{O}(n\!\cdot\!m)</math> forward steps of the current arcs of all nodes in total. So, it suffices to show that there are <math>\mathcal{O}(n^2)</math> non-saturating push steps in each scaling phase. To see that, we consider the following, dynamically changing '''potential function''':
The [[Preflow-push#Complexity|complexity considerations]] for the [[Preflow-push|generic preflow-push algorithm]] yield <math>\mathcal{O}(n^2)</math> relabel steps and forward steps of current arcs, and <math>\mathcal{O}(n\!\cdot\!m)</math> saturating push steps. Due to the above implementation of point 3, all node selections have complexity <math>\mathcal{O}(P+n\cdot\log U)</math> in total, where <math>P</math> is the total number of saturating and non-saturating push steps.
:<math>\Phi:=\sum_{v\in V\setminus\{s,t\}}e_f(v)\cdot d(v)/\Delta</math>.
The arguments of <math>\Phi</math> are evident, so they are omitted for convenience. Since <math>e_f(v)\leq\Delta</math>, all relabel steps together cannot increase <math>\Phi</math> by more than <math>2n^2</math> (cf. [[Preflow-push#Complexity|here]]). Each push step - saturating or not - decreases this value because excess is always sent from a node with a higher <math>d</math>-label to a node with a (one unit) lower <math>d</math>-label. Therefore, we may safely ignore saturating push steps. Now, a non-saturating push sends at least <math>\Delta/2</math> units of excess, which decreases <math>\Phi</math> by <math>1/2</math>. Consequently, the number of non-saturating push steps is in <math>\mathcal{O}(n^2)</math>.
 
Due to the above implementation of point 3, all node selections have complexity <math>\mathcal{O}(P+n\cdot\log U)</math>, where <math>P</math> is the total number of push steps. In summary, the claim follows.


So, it suffices to show that there are <math>\mathcal{O}(n^2)</math> non-saturating push steps in each scaling phase. To see that, we consider the following, dynamically changing '''potential function''':
:<math>\Phi(f,d):=\sum_{v\in V\setminus\{s,t\}}\frac{e_f(v)}{\Delta}\cdot d(v)</math>.
Since <math>e_f(v)\leq\Delta</math>, it is <math>\Phi(f,d)\leq\sum_{v\in V\setminus\{s,t\}}d(v)</math>, so all relabel steps together cannot increase <math>\Phi</math> by more than <math>2n^2</math> (cf. [[Preflow-push#Complexity|here]]). Each push step - saturating or not - decreases the value of <math>\Phi</math> because excess is always sent from a node with a higher <math>d</math>-label to a node with a (one unit) lower <math>d</math>-label. Therefore, we may safely ignore saturating push steps. Now, a non-saturating push sends at least <math>\Delta/2</math> units of excess, which decreases <math>\Phi</math> by at least <math>1/2</math>. Consequently, the number of non-saturating push steps is in <math>\mathcal{O}(n^2)</math> in each scaling phase.


'''Remark:'''
'''Remark:'''
Potential functions are a general concept for complexity considerations. The sum and the maximum of all <math>d</math>-labels are simpler potential functions, which are used for the complexity considerations for the [[Preflow-push|generic pre flow-push algorithm]] and for the [[FIFO preflow-push#Correctness|FIFO variant]], respectively.
Potential functions are a general concept for complexity considerations. The sum and the maximum of all <math>d</math>-labels are rather simple examples of potential functions, which are used for the complexity considerations for the [[Preflow-push|generic pre flow-push algorithm]] and for the [[FIFO preflow-push#Correctness|FIFO variant]], respectively.

Latest revision as of 17:29, 18 December 2017

Abstract view

Algorithmic problem: max-flow problem (standard version)

This is a specialization and slight modification of the generic preflow-push algorithm:

  1. An additional nonnegative integral number [math]\displaystyle{ \Delta }[/math] is maintained, which is initialized so as to be at least as large as the largest value [math]\displaystyle{ e_f }[/math] (but not more than the next higher power of 2 for complexity reasons, cf. here).
  2. In each iteration, an active node [math]\displaystyle{ v }[/math] may only be chosen if it has large excess, that is, [math]\displaystyle{ e_f(v)\geq\Delta/2 }[/math].
  3. Among all active nodes with large excess, we choose one with minimum [math]\displaystyle{ d }[/math]-label.
  4. The flow value pushed over an arc [math]\displaystyle{ (v,w) }[/math] from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] must be small enough so the excess of [math]\displaystyle{ w }[/math] does not exceed [math]\displaystyle{ \Delta }[/math] afterwards. In other words, the flow value to be pushed over [math]\displaystyle{ (v,w) }[/math] is not the minimum of [math]\displaystyle{ v }[/math]'s excess and the residual capacity of [math]\displaystyle{ (v,w) }[/math] as in the generic preflow-push algorithm; here it is the minimum of these two values and a third value, [math]\displaystyle{ \Delta-e_f(w) }[/math], where [math]\displaystyle{ f }[/math] denotes the current preflow immediately before this push operation.
  5. If there are active nodes but none with large excess, we do not apply a push or relabel operation but reset [math]\displaystyle{ \Delta:=\Delta/2 }[/math] (integral division) repeatedly until there is an active node with large excess.

Invariant:

  1. All invariants of the generic pre-flow push algorithm.
  2. At any time, it is [math]\displaystyle{ e_f(v)\leq\Delta }[/math] for every node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].

Variant: The variant of the generic pre-flow push algorithm is extended by a fourth option: The value of [math]\displaystyle{ \Delta }[/math] is reduced to [math]\displaystyle{ \Delta/2 }[/math].

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.

Implementation of point 3 of the abstract algorithm

All active nodes with large excess are stored in an array of sets of nodes. The list at index [math]\displaystyle{ k }[/math] contains all active nodes [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math] with large excess and [math]\displaystyle{ d(v)=k }[/math]. This array is computed from scratch in the initialization and after every reduction of [math]\displaystyle{ \Delta }[/math]. A current array index is maintained, which is not larger than the index of any non-empty node set in the array. Whenever a node is to be chosen, the current array index is increased as long as the list at the current array index is empty. A push step may result in a new active node with large excess. However, this node has to be inserted at the index immediately before the current array index, so the current array index is never decreased by more than one unit at a time.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m+n^2\!\cdot\!\log U) }[/math], where [math]\displaystyle{ n=|V| }[/math], [math]\displaystyle{ m=|A| }[/math], and [math]\displaystyle{ U=\max\{u(a)|a\in A\} }[/math].

Proof: The complexity considerations for the generic preflow-push algorithm yield [math]\displaystyle{ \mathcal{O}(n^2) }[/math] relabel steps and forward steps of current arcs, and [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m) }[/math] saturating push steps. Due to the above implementation of point 3, all node selections have complexity [math]\displaystyle{ \mathcal{O}(P+n\cdot\log U) }[/math] in total, where [math]\displaystyle{ P }[/math] is the total number of saturating and non-saturating push steps.

So, it suffices to show that there are [math]\displaystyle{ \mathcal{O}(n^2) }[/math] non-saturating push steps in each scaling phase. To see that, we consider the following, dynamically changing potential function:

[math]\displaystyle{ \Phi(f,d):=\sum_{v\in V\setminus\{s,t\}}\frac{e_f(v)}{\Delta}\cdot d(v) }[/math].

Since [math]\displaystyle{ e_f(v)\leq\Delta }[/math], it is [math]\displaystyle{ \Phi(f,d)\leq\sum_{v\in V\setminus\{s,t\}}d(v) }[/math], so all relabel steps together cannot increase [math]\displaystyle{ \Phi }[/math] by more than [math]\displaystyle{ 2n^2 }[/math] (cf. here). Each push step - saturating or not - decreases the value of [math]\displaystyle{ \Phi }[/math] because excess is always sent from a node with a higher [math]\displaystyle{ d }[/math]-label to a node with a (one unit) lower [math]\displaystyle{ d }[/math]-label. Therefore, we may safely ignore saturating push steps. Now, a non-saturating push sends at least [math]\displaystyle{ \Delta/2 }[/math] units of excess, which decreases [math]\displaystyle{ \Phi }[/math] by at least [math]\displaystyle{ 1/2 }[/math]. Consequently, the number of non-saturating push steps is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math] in each scaling phase.

Remark: Potential functions are a general concept for complexity considerations. The sum and the maximum of all [math]\displaystyle{ d }[/math]-labels are rather simple examples of potential functions, which are used for the complexity considerations for the generic pre flow-push algorithm and for the FIFO variant, respectively.