Linear Assignment Problem


The Hungarian Algorithm solves instances of the assignment problem. This section links to two applets: the Basic O(n4) implementation, and the advanced O(n3) implementation.


This is a Java application: the latest version of Java is therefore recommended.


To install this app, you can:


The Java Applet starts with a sample cost matrix, that can be modified by double clicking on the cells. The applet shows the various steps during the execution, both on the matrix and on the corresponding bipartite graph. It is possible to interact with the execution through the buttons

The command File -> Open in the menu bar allows to insert a new cost matrix, by loading a file written in xml-standard, according to the following template. The tag matrix wraps all the rows, and represents the root node of the xml tree. Each sub-node is identified by the row number (R1, R2, etc..) and has as many attributes as the number of columns, each one containing the cost value (e.g., e1="5" e2="2" e3="3" e4="4" ...).

For example, an input file can be like this one:

     <R1 e1="5" e2="2" e3="3" e4="4"/>
     <R2 e1="7" e2="8" e3="4" e4="5"/>
     <R3 e1="6" e2="3" e3="5" e4="6"/>
     <R4 e1="2" e2="2" e3="3" e4="5"/>

The cost matrix can also be edited through the command Edit -> Cost Matrix Dimension. Once the dimension has been defined, a null cost matrix is instantiated, which can be modified by double clicking on the cells.

The command File -> Save As allows to store the cost matrix in an xml file.



Other algorithms

Papamanthou, Samaras and Paparrizos implemented didactic applets for the Assignment Problem and the Transportation Problem. For both problems, four algorithms are presented: the network primal simplex algorithm, and three implementations of an exterior point algorithm (respectively initialized with a Balinski Tree, an AKP Tree and a Simple Start Tree).

The Java applets are here.