🚀 go-pugleaf

In article <1992Oct14.043850.4095@pslu1.psl.wisc.edu> emmel@pslu1.psl.wisc.edu (Grant Emmel) writes:
>I'm looking for available software (public domain or not) for a
>non-commercial/non-educational application (I'm helping a friend)
>that will solve the assignment problem.  That is the general idea.
>
>Any help, from theory to software would be helpful.  Post if it is
>interesting enough, email in any case.
>Grant Emmel

A simple example of the assignment problem would be: There are n jobs 
and n different candidates for these jobs. We want to assign one 
and only one candidate to each job. There is a cost square matrix that
specifies the cost that has to be paid for candidate i to perform job
j, i=1,..,n, j=1,.., n. The objective is to minimize the cost.
The method which is used usually to solve the assignment problem is 
the "Hungarian method". It is a dual algorithm. The complexity is 
O(n^3). For a full description of the algorithm you can refer to 
"Linear and combinatorial programming" by K.G. Murty. It is in 
Chapter 12: Networ Algorithms. A more sophisticated approach is 
in "Network Programming" by the same author (This book was published
a few months ago so it may be hard to find it) from Prentice Hall.
The code should not be hard to write.
-Samer