Hungarian algorithm

Previous: Brute force Up: The pairing step

Hungarian algorithm

A reference to this algorithm was first found in [12][chapter 11]. The Hungarian algorithm is an instance of the bipartite weighted matching problem.

The algorithm given in this reference is an application of a linear programming method called the Simplex method. Linear programming methods are often used to optimize equations. The quark-antiquark assignment problem can be re-stated as follows:

Unfortunately, the algorithm given for the solution does not appear to work, even on paper.

Further research to find another reference to the algorithm resulted in several much vaguer descriptions of the solution in terms of the Simplex. The descriptions were sufficiently vague as to agree with the first reference.

mcr@ccs.carleton.ca