List of Selected Number of Optimal Solutions of the Assignment Problem by Time Criterion
Lasko M. Laskov, Marin L. Marinov · 2022
In this paper we present a solution of the assignment problem with an algorithm with complexity $O\left({{n^{\frac{9}{2}}}}\right)$. The discussed algorithm allows an effective approach for generation of a list of selected number of optimal solutions of this problem. If it is predefined that the list does not contain more than n0number of optimal solutions, then the proposed algorithm has complexity $\tilde nO\left({{n^{\frac{9}{2}}}}\right)$, where $\tilde n = \min \left\{ {{n_0},{n_1}} \right\}$ with n1being the number of perfect matchings in the graph. The method is based on the Hopcroft-Karp algorithm for maximum matching in a bipartite graphs [16].