linear assignment problem について

Hungarian algorithm が有名所。scipy はこのアルゴリズムで実装されている。

>>> cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])
>>> from scipy.optimize import linear_sum_assignment
>>> row_ind, col_ind = linear_sum_assignment(cost)
>>> col_ind
array([1, 0, 2])
>>> cost[row_ind, col_ind].sum()
5

brilliant.org

  1. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing, vol. 38, pp. 325-340, 1987.

This paper is not publicly available though a brief description exists on sciencedirect.com. JV is faster in than the Hungarian algorithm in practice, though the complexity is the same - O(n3).

blog.sourced.tech