Hungarian algorithm: Difference between revisions

Revision as of 07:15, 15 November 2021

Revision as of 07:19, 15 November 2021

Line 66:

:<math>\Delta := \min \{c(i,j)-y(i)-y(j): i \in Z \cap S, j \in T \setminus Z\}.</math>

<{{math>\|&Delta</math>;}} is well defined because at least one such edge <math>ij</math> must exist whenever the matching is not yet of maximum possible size (see the following section); it is positive because there are no tight edges between <math>Z \cap S</math> and <math>T \setminus Z</math>. Increase {{mvar|y}} by <{{math>\|&Delta</math>;}} on the vertices of <math>Z \cap S</math> and decrease {{mvar|y}} by <{{math>\|&Delta</math>;}} on the vertices of <math>Z \cap T</math>. The resulting {{mvar|y}} is still a potential, and although the graph <math>G_y</math> changes, it still contains {{mvar|M}} (see the next subsections). We orient the new edges from {{mvar|S}} to {{mvar|T}}. By the definition of <{{math>\|&Delta</math>;}} the set {{mvar|Z}} of vertices reachable from <math>R_S</math> increases (note that the number of tight edges does not necessarily increase).

We repeat these steps until {{mvar|M}} is a perfect matching, in which case it gives a minimum cost assignment. The running time of this version of the method is <math>O(n^4)</math>: {{mvar|M}} is augmented {{mvar|n}} times, and in a phase where {{mvar|M}} is unchanged, there are at most {{mvar|n}} potential changes (since {{mvar|Z}} increases every time). The time sufficient for a potential change is <math>O(n^2)</math>.

Line 75:

* {{mvar|M}} is of maximum possible size.

* <math>G_y</math> contains an augmenting path.

* {{mvar|G}} contains a '''loose-tailed path''': a path from some vertex in <math>R_S</math> to a vertex in <math>T \setminus Z</math> that consists of any number (possibly zero) of tight edges followed by a single loose edge. The trailing loose edge of a loose-tailed path is thus from <math>Z \cap S</math>, guaranteeing that <{{math>\|&Delta</math>;}} is well defined.

If {{mvar|M}} is of maximum possible size, we are of course finished. Otherwise, by [[Berge's lemma]], there must exist an augmenting path {{mvar|P}} with respect to {{mvar|M}} in the underlying graph {{mvar|G}}. However, this path may not exist in <math>G_y</math>: Although every even-numbered edge in {{mvar|P}} is tight by the definition of {{mvar|M}}, odd-numbered edges may be loose and thus absent from <math>G_y</math>. One endpoint of {{mvar|P}} is in <math>R_S</math>, the other in <math>R_T</math>; w.l.o.g., suppose it begins in <math>R_S</math>. If every edge on {{mvar|P}} is tight, then it remains an augmenting path in <math>G_y</math> and we are done. Otherwise, let <math>uv</math> be the first loose edge on {{mvar|P}}. If <math>v \notin Z</math> then we have found a loose-tailed path and we are done. Otherwise, {{mvar|v}} is reachable from some other path {{mvar|Q}} of tight edges from a vertex in <math>R_S</math>. Let <math>P_v</math> be the subpath of {{mvar|P}} beginning at {{mvar|v}} and continuing to the end, and let <math>P'</math> be the path formed by travelling along {{mvar|Q}} until a vertex on <math>P_v</math> is reached, and then continuing to the end of <math>P_v</math>. Observe that <math>P'</math> is an augmenting path in {{mvar|G}} with at least one fewer loose edge than {{mvar|P}}. {{mvar|P}} can be replaced with <math>P'</math> and this reasoning process iterated (formally, using induction on the number of loose edges) until either an augmenting path in <math>G_y</math> or a loose-tailed path in {{mvar|G}} is found.

Line 83:

===Proof that {{mvar|y}} remains a potential===

To show that {{mvar|y}} remains a potential after being adjusted, it suffices to show that no edge has its total potential increased beyond its cost. This is already established for edges in {{mvar|M}} by the preceding paragraph, so consider an arbitrary edge {{mvar|uv}} from {{mvar|S}} to {{mvar|T}}. If <math>y(u)</math> is increased by <{{math>\|&Delta</math>;}}, then either <math>v \in Z \cap T</math>, in which case <math>y(v)</math> is decreased by <{{math>\|&Delta</math>;}}, leaving the total potential of the edge unchanged, or <math>v \in T \setminus Z</math>, in which case the definition of <{{math>\|&Delta</math>;}} guarantees that <math>y(u)+y(v)+\Delta \leq c(u,v)</math>. Thus {{mvar|y}} remains a potential.

==Matrix interpretation==