Home

This is an single/multi threaded C++ implementation of Bertsekas' asymmetric auction algorithm found here. It's used to find the best association from rows to columns based on weights stored in a matrix.

Input:

• dense matrix of type Eigen::Matrix see
• sparse matrix which stores in CRS and CCS-Matrix (will be changed to eigen sparse type)

Output:

• vector of edges, i.e. 3-tuple of row, column and it's weight

Issues:

• Only use weights between 0 and 1 (real coefficients), otherwise it will not work
• be sure that the matrix has rows <= cols, otherwise transpose it
• assert that the problem has a feasible solution (i.e. number of possible associations = min(#rows, #cols))
• currently there's no epsilon scaling, the value of epsilon might be chosen by yourself (otherwise wrong solutions could be found)
• the multithreaded implementation is just usefull for very large problems (depending on cpu)
• currently the conversion of dense eigen matrix type to the selfmade sparse type takes some time