Hungarian method

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:

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].

Invariant:

1. [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math].
2. 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:

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],

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: 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].