Hungarian method: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(39 intermediate revisions by the same user not shown)
Line 39: Line 39:
'''Abstract view:'''
'''Abstract view:'''
# Let <math>G'=(V,E')</math> be the subgraph of <math>G</math> where <math>E'</math> comprises all feasible edges.
# Let <math>G'=(V,E')</math> be the subgraph of <math>G</math> where <math>E'</math> comprises all feasible edges.
# Try to [[Matchings in graphs#Finding augmenting paths|find]] an [[Matchings in graphs#Alternating and augmenting paths|augmenting path]] in <math>G'</math> with respect to <math>M</math>.
# Try to find an [[Matchings in graphs#Alternating and augmenting paths|augmenting path]] in <math>G'</matH> with respect to <math>M</math>.
# If step 2 succeeds, [[Matchings in graphs#Alternating and augmenting paths|augment]] <math>M</math> along this path.
# If step 2 succeeds[[Matchings in graphs#Alternating and augmenting paths|augment]] <math>M</math> along this path.
# Otherwise:
# Otherwise:
## Choose some exposed node <math>v\in V_1</math>.
## Choose some exposed node <math>v\in V_1</math>.
## Initialize two [[Sets and sequences|sets]], <math>S:=\{v\}</math>, <math>T:=\emptyset</math>.
## Initialize two dynamically growing node [[Sets and sequences|sets]], <math>S:=\{v\}</math> and <math>T:=\emptyset</math> and a dynamically growing [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] <math>(S\dot\cup T,E_A)</math> by <math>E_A:=\emptyset</math>.
## While <math>T\subsetneq N(S)</math>:
## While <math>T\subsetneq N(S)</math>:
### Let <math>w\in N(S)\setminus T</math>.
### Let <math>w\in N(S)\setminus T</math> and let <math>u\in S</math> such that <math>\{u,w\}\in E'</math>.
### Let <math>\{u,w\}</math> be the unique edge incident to <math>w</math> that is in <math>M</math>.
### Insert <math>w</math> in <math>T</math> and <math>(u,w)</math> in <math>E_A</math>.
### Insert <math>w</math> in <math>T</math> and <math>u</math> in <math>S</math> (if <math>u</math> is not yet in <math>S</math>).
### Let <math>\{u',w\}</math> be the unique edge incident to <math>w</math> that is in <math>M</math>.
## Set <math>\delta:=\min\{c(\{u,w\})-x(u)-y(w)|u\in S,w\in V_2\setminus T\}</math>.
### Insert <math>u'</math> in <math>S</math> and <math>(w,u')</math> in <math>E_A</math>.
## Set <math>\delta:=\min\{x(u)+y(w)-c(\{u,w\})|u\in S,w\in V_2\setminus T\}</math>.
## For all <math>u\in S</math>, decrease <math>x(u)</math> by <math>\delta</math>.
## For all <math>u\in S</math>, decrease <math>x(u)</math> by <math>\delta</math>.
## For all <math>w\in T</math>, increase <math>y(w)</math> by <math>\delta</math>.
## For all <math>w\in T</math>, increase <math>y(w)</math> by <math>\delta</math>.
Line 56: Line 57:


'''Proof:'''
'''Proof:'''
Note that <math>w</math> is indeed matched because, otherwise, step 2 had found an augmenting path. Hence, step 4.3.2 is well defined (the only step for which this fact is not obvious).
Note that <math>w</math> is indeed matched in step 4.3.3 because, otherwise, step 2 had found an augmenting path. Hence, step 4.3.2 is well defined (the only step for which this fact is not obvious).


The second point of the invariant is clear, so consider the first point. We have to show that steps 4.4-4.6 maintain the first point of the invariant. Let <math>v\in V_1</math> and <math>w\in V_2</math>. If <math>w\in T</math>, <math>x(v)+y(w)</math> cannot decrease, so consider the case <math>w\not\in T</math>. If <math>v\not\in S</math>, <math>x(v)+y(w)</math> does not change, so let <math>v\in S</math>. In this case, the specific choice of <math>\delta</math> ensures the first point of the invariant.
The second point of the invariant is clear, so consider the first point. More specifically, we have to show that steps 4.4-4.6 maintain the first point of the invariant. Let <math>v\in V_1</math> and <math>w\in V_2</math>. If <math>w\in T</math>, <math>x(v)+y(w)</math> cannot decrease, so consider the case <math>w\not\in T</math>. If <math>v\not\in S</math>, <math>x(v)+y(w)</math> does not change, so let <math>v\in S</math>. In this case, the specific choice of <math>\delta</math> ensures the first point of the invariant.


In particular, these observations ensure that each edge that is feasible immediately before the current iteration, is also feasible immediately after the current iteration. The specific choice of <math>\delta>0</math> implies that at least one more edge will become feasible.
In particular, these observations ensure that each edge that is feasible immediately before the current iteration, is also feasible immediately after the current iteration. The specific choice of <math>\delta>0</math> implies that at least one more edge will become feasible.
Line 64: Line 65:
== Correctness ==
== Correctness ==


Termination of the main loop will follow from the complexity considerations below. Let <math>M</math> be a perfect matching and <math>x</math> and <math>y</math> be given such that <math>c(e)=x(v)+y(w)</math> for all <math>e=\{v,w\}\in M</math>, where <math>v\in V_1</math> and <math>w\in V_2</math>. Let <math>M'</math> be another matching. Due to the invariant, it is
Termination of the main loop will follow from the complexity considerations below. It remains to show that <math>M</math> is a maximum-weight perfect matching on termination. Perfectness follows from the break condition, so it suffices to prove weight-maximality.
:<math>c(M)=\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M}c(e)=\sum_{v\in V_1}x(v)+\sum_{w\in V_2}y(w)\geq\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M'}c(e)</math>.
 
Let <math>M'</math> be another matching. Due to the invariant, it is
:<math>c(M)=\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M}c(e)=\sum_{v\in V_1}x(v)+\sum_{w\in V_2}y(w)\geq\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M'}c(e)=c(M')</math>.
Therefore, <math>M</math> is maximal.
Therefore, <math>M</math> is maximal.


'''Remark:'''
'''Remark:'''
In particular, the following equivalence is proved: A perfect matching <math>M</math> has maximum weight if, and only if, there are <math>x</math> and <math>y</math> such that <math>c(e)=x(v)+y(w)</math> for all <math>e=\{v,w\}\in M</math>.
In particular, the following equivalence is proved: A perfect matching <math>M</math> has maximum weight if, and only if, there are <math>x</math> and <math>y</math> such that <math>c(e)=x(v)+y(w)</math> for all <math>e=\{v,w\}\in M</math>.
== Complexity ==


'''Statement:'''
'''Statement:'''
Line 75: Line 80:


'''Proof:'''
'''Proof:'''
Steps 4-6 are executed at most <math>n</math> times because each time the number of feasible edges increases, and no feasible edge becomes infeasible at any stage. On the other hand, <math>|M|</math> is increased at most <math>n</math> times as well. In summary, the number of iterations of the main loop is in <math>\mathcal{O}(n)</math>. In an iteration, each of the <math>(n/2)^2</math> edges is touched at most once, which yields the claim.
Step 2 is executed <math>\mathcal{O}(n)</math> times in total because each time <math>|M|</math> is increased and <math>|M|</math> is never decreased. Each execution of step 2 requires <math>\mathcal{O}(m)\subset\mathcal{O}(n^2)</math> time.
 
Steps 3+4 are executed <math>\mathcal{O}(n^2)</math> times because every execution creates a new feasible edge, and no edge ever becomes infeasible. Each execution of steps 3+4 requires <math>\mathcal{O}(n)</math> time.

Latest revision as of 17:26, 27 February 2015

Abstract view

Algorithmic problem: Maximum-weight matching in complete bipartite graphs [math]\displaystyle{ G=(V_1\dot\cup V_2,E) }[/math] with [math]\displaystyle{ |V_1|=|V_2| }[/math].

Type of algorithm: loop.

Auxiliary data:

  1. A real number [math]\displaystyle{ x(v) }[/math] for each node [math]\displaystyle{ v\in V_1 }[/math].
  2. A real number [math]\displaystyle{ y(w) }[/math] for each node [math]\displaystyle{ w\in V_2 }[/math].

Definition: For node values [math]\displaystyle{ (x,y) }[/math], an edge [math]\displaystyle{ e=\{v,w\}\in E }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], is feasible if [math]\displaystyle{ c(e)=x(v)+y(w) }[/math].

Invariant:

  1. For each edge [math]\displaystyle{ e=\{v,w\}\in E }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)\leq x(v)+y(w) }[/math].
  2. [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math] and all edges of [math]\displaystyle{ M }[/math] are feasible.

Variant: In each iteration, one of the following two changes will occur:

  1. [math]\displaystyle{ |M| }[/math] increases by one.
  2. The number of feasible edges increases.

Break condition: [math]\displaystyle{ M }[/math] is a perfect matching.

Induction basis

  1. Set [math]\displaystyle{ M:=\emptyset }[/math].
  2. Initialize all [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] values such that the invariant is fulfilled, for example:
    1. [math]\displaystyle{ x(v):=\max\{c(\{v,w\})|w\in V_2\} }[/math] for all [math]\displaystyle{ v\in V_1 }[/math].
    2. [math]\displaystyle{ y(w):=0 }[/math] for all [math]\displaystyle{ w\in V_2 }[/math].

Induction step

Notation:

  1. For a node [math]\displaystyle{ v\in V_1 }[/math]: [math]\displaystyle{ N(v):=\{w\in V_2|c(\{v,w\})=x(v)+y(w)\} }[/math], the "neighbors" of [math]\displaystyle{ v }[/math].
  2. For a set [math]\displaystyle{ S\subseteq V_1 }[/math]: [math]\displaystyle{ N(S):=\bigcup_{v\in S}N(v) }[/math].

Abstract view:

  1. Let [math]\displaystyle{ G'=(V,E') }[/math] be the subgraph of [math]\displaystyle{ G }[/math] where [math]\displaystyle{ E' }[/math] comprises all feasible edges.
  2. Try to find an augmenting path in [math]\displaystyle{ G' }[/math] with respect to [math]\displaystyle{ M }[/math].
  3. If step 2 succeeds: augment [math]\displaystyle{ M }[/math] along this path.
  4. Otherwise:
    1. Choose some exposed node [math]\displaystyle{ v\in V_1 }[/math].
    2. Initialize two dynamically growing node sets, [math]\displaystyle{ S:=\{v\} }[/math] and [math]\displaystyle{ T:=\emptyset }[/math] and a dynamically growing arborescence [math]\displaystyle{ (S\dot\cup T,E_A) }[/math] by [math]\displaystyle{ E_A:=\emptyset }[/math].
    3. While [math]\displaystyle{ T\subsetneq N(S) }[/math]:
      1. Let [math]\displaystyle{ w\in N(S)\setminus T }[/math] and let [math]\displaystyle{ u\in S }[/math] such that [math]\displaystyle{ \{u,w\}\in E' }[/math].
      2. Insert [math]\displaystyle{ w }[/math] in [math]\displaystyle{ T }[/math] and [math]\displaystyle{ (u,w) }[/math] in [math]\displaystyle{ E_A }[/math].
      3. Let [math]\displaystyle{ \{u',w\} }[/math] be the unique edge incident to [math]\displaystyle{ w }[/math] that is in [math]\displaystyle{ M }[/math].
      4. Insert [math]\displaystyle{ u' }[/math] in [math]\displaystyle{ S }[/math] and [math]\displaystyle{ (w,u') }[/math] in [math]\displaystyle{ E_A }[/math].
    4. Set [math]\displaystyle{ \delta:=\min\{x(u)+y(w)-c(\{u,w\})|u\in S,w\in V_2\setminus T\} }[/math].
    5. For all [math]\displaystyle{ u\in S }[/math], decrease [math]\displaystyle{ x(u) }[/math] by [math]\displaystyle{ \delta }[/math].
    6. For all [math]\displaystyle{ w\in T }[/math], increase [math]\displaystyle{ y(w) }[/math] by [math]\displaystyle{ \delta }[/math].

Remark: Steps 2-4 can be folded into one loop, which breaks if [math]\displaystyle{ N(S)=T }[/math] or an exposed node (and thus an augmenting path) is found.

Proof: Note that [math]\displaystyle{ w }[/math] is indeed matched in step 4.3.3 because, otherwise, step 2 had found an augmenting path. Hence, step 4.3.2 is well defined (the only step for which this fact is not obvious).

The second point of the invariant is clear, so consider the first point. More specifically, we have to show that steps 4.4-4.6 maintain the first point of the invariant. Let [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math]. If [math]\displaystyle{ w\in T }[/math], [math]\displaystyle{ x(v)+y(w) }[/math] cannot decrease, so consider the case [math]\displaystyle{ w\not\in T }[/math]. If [math]\displaystyle{ v\not\in S }[/math], [math]\displaystyle{ x(v)+y(w) }[/math] does not change, so let [math]\displaystyle{ v\in S }[/math]. In this case, the specific choice of [math]\displaystyle{ \delta }[/math] ensures the first point of the invariant.

In particular, these observations ensure that each edge that is feasible immediately before the current iteration, is also feasible immediately after the current iteration. The specific choice of [math]\displaystyle{ \delta\gt 0 }[/math] implies that at least one more edge will become feasible.

Correctness

Termination of the main loop will follow from the complexity considerations below. It remains to show that [math]\displaystyle{ M }[/math] is a maximum-weight perfect matching on termination. Perfectness follows from the break condition, so it suffices to prove weight-maximality.

Let [math]\displaystyle{ M' }[/math] be another matching. Due to the invariant, it is

[math]\displaystyle{ c(M)=\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M}c(e)=\sum_{v\in V_1}x(v)+\sum_{w\in V_2}y(w)\geq\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M'}c(e)=c(M') }[/math].

Therefore, [math]\displaystyle{ M }[/math] is maximal.

Remark: In particular, the following equivalence is proved: A perfect matching [math]\displaystyle{ M }[/math] has maximum weight if, and only if, there are [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] such that [math]\displaystyle{ c(e)=x(v)+y(w) }[/math] for all [math]\displaystyle{ e=\{v,w\}\in M }[/math].

Complexity

Statement: The asymptotic worst-case complexity is in [math]\displaystyle{ \mathcal{O}(n^3) }[/math], where [math]\displaystyle{ n=|V| }[/math].

Proof: Step 2 is executed [math]\displaystyle{ \mathcal{O}(n) }[/math] times in total because each time [math]\displaystyle{ |M| }[/math] is increased and [math]\displaystyle{ |M| }[/math] is never decreased. Each execution of step 2 requires [math]\displaystyle{ \mathcal{O}(m)\subset\mathcal{O}(n^2) }[/math] time.

Steps 3+4 are executed [math]\displaystyle{ \mathcal{O}(n^2) }[/math] times because every execution creates a new feasible edge, and no edge ever becomes infeasible. Each execution of steps 3+4 requires [math]\displaystyle{ \mathcal{O}(n) }[/math] time.