Proceedings of the 2nd International Conference on Advances in Mechanical Engineering and Industrial Informatics (AMEII 2016)

<Previous Article In Volume
Next Article In Volume>

Solving large-scale assignment problems by Kuhn-Munkres algorithm

Authors
Hong Cui, Jingjing Zhang, Chunfeng Cui, Qinyu Chen
Corresponding Author
Hong Cui
Available Online April 2016.
DOI
10.2991/ameii-16.2016.160How to use a DOI?
Keywords
Assignment problem, Kuhn-Munkres algorithm, sparse-KM, parallel-KM
Abstract

Kuhn-Munkres algorithm is one of the most popular polynomial time algorithms for solving classical assignment problem. The assignment problem is to find an assignment of the jobs to the workers that has minimum cost, given a cost matrix X 2 Rm n, where the element in the i-th row and j-th column represents the cost of assigning the i-th job to the j-th worker. the time complexity of Kuhn-Munkres algorithm is O(mn2), which brings prohibitive computational burden on large scale matrices, limiting the further usage of these methods in real applications. Motivated by this observation, a series of acceleration skills and parallel techniques have been studied on special structure. In this paper, we improve the original Kuhn-Munkres algorithm by utilizing the sparsity structure of the cost matrix, and propose two algorithms, sparsity based KM(sKM) and parallel KM(pKM). Furthermore, numerical experiments are given to show the efficiency of our algorithm. We empirically evaluate the proposed algorithm sKM) and (pKM) on random generated largescale datasets. Results have shown that sKM) greatly improves the computational performance. At the same time, (pKM) provides a parallel way to solve assignment problem with considerable accuracy loss.

Copyright
© 2016, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the 2nd International Conference on Advances in Mechanical Engineering and Industrial Informatics (AMEII 2016)
Series
Advances in Engineering Research
Publication Date
April 2016
ISBN
978-94-6252-188-9
ISSN
2352-5401
DOI
10.2991/ameii-16.2016.160How to use a DOI?
Copyright
© 2016, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

risenwbib
TY  - CONF
AU  - Hong Cui
AU  - Jingjing Zhang
AU  - Chunfeng Cui
AU  - Qinyu Chen
PY  - 2016/04
DA  - 2016/04
TI  - Solving large-scale assignment problems by Kuhn-Munkres algorithm
BT  - Proceedings of the 2nd International Conference on Advances in Mechanical Engineering and Industrial Informatics (AMEII 2016)
PB  - Atlantis Press
SP  - 822
EP  - 827
SN  - 2352-5401
UR  - https://doi.org/10.2991/ameii-16.2016.160
DO  - 10.2991/ameii-16.2016.160
ID  - Cui2016/04
ER  -