Linear Bottleneck Assignment Problem


The Threshold Algorithm solves instances of the linear bottleneck assignment problem.


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.