Hungarian algorithm: Difference between revisions

Revision as of 16:37, 31 March 2024

Revision as of 06:33, 9 April 2024

Line 337:

==Matrix interpretation==

This variant of the algorithm follows the formulation given by Flood,<ref name="flood">{{cite journal | last=Flood | first=Merrill M. | title=The Traveling-Salesman Problem | journal=Operations Research | volume=4 | issue=1 | date=1956 | issn=0030-364X | doi=10.1287/opre.4.1.61 | pages=61–75}}</ref>, and later described more explicitly by Munkres, who proved it runs in <math>\mathcal{O}(n^4)</math> time.<ref name="munkres"/> Instead of keeping track of the potentials of the vertices, the algorithm operates only on a matrix:

:<math>a_{ij}:=c(i,j)-y(i)-y(j)</math>