Hungarian method: Difference between revisions
| Line 30: | Line 30: | ||
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. 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 | ||
:<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>. | :<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>. | ||
Therefore, <math>M</math> is maximal. | |||
'''Remark:''' | |||
The algorithm even proves equivalence: 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>. | |||
Revision as of 19:39, 22 November 2014
Abstract view
Algorithmic problem: Maximum-weight matching in complete bipartite graphs [math]\displaystyle{ G=(V_1\dot\cup V_2,E) }[/math].
Type of algorithm: loop.
Auxiliary data:
- A real number [math]\displaystyle{ x(v) }[/math] for each node [math]\displaystyle{ v\in V_1 }[/math].
- A real number [math]\displaystyle{ y(w) }[/math] for each node [math]\displaystyle{ w\in V_2 }[/math].
Invariant:
- [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math].
- For each edge [math]\displaystyle{ e=\{v,w\}\in M }[/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].
Variant:
Break condition: For each edge [math]\displaystyle{ e=\{v,w\} in M }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)=x(v)+y(w) }[/math].
Induction basis
Initialize all [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] values such that the invariant is fulfilled, for example:
- [math]\displaystyle{ x(v):=\max\{c(\{v,w\})|w\in V_2\} }[/math] for all [math]\displaystyle{ v\in V_1 }[/math].
- [math]\displaystyle{ y(w):=0 }[/math] for all [math]\displaystyle{ w\in V_2 }[/math],
Induction step
Correctness
Termination of the main loop will follow from the complexity considerations below. Let [math]\displaystyle{ M }[/math] be a perfect matching and [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] be given such that [math]\displaystyle{ c(e)=x(v)+y(w) }[/math] for all [math]\displaystyle{ e=\{v,w\}\in M }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w/in V_2 }[/math]. 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) }[/math].
Therefore, [math]\displaystyle{ M }[/math] is maximal.
Remark: The algorithm even proves equivalence: 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>c(e)=x(v)+y(w)</math> for all [math]\displaystyle{ e=\{v,w\}\in M }[/math].