Multiple Hungarian Method for k -Assignment Problem

Boštjan Gabrovšek, Tina Novak, Janez Povh, Darja Rupnik Poklukar and Janez Žerovnik
Additional contact information
Boštjan Gabrovšek: Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia
Tina Novak: Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia
Janez Povh: Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia
Darja Rupnik Poklukar: Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia
Janez Žerovnik: Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia

Mathematics, 2020, vol. 8, issue 11, 1-18

Abstract: The k -assignment problem (or, the k -matching problem) on k -partite graphs is an NP-hard problem for k ≥ 3 . In this paper we introduce five new heuristics. Two algorithms, B m and C m , arise as natural improvements of Algorithm A m from (He et al., in: Graph Algorithms And Applications 2, World Scientific, 2004). The other three algorithms, D m , E m , and F m , incorporate randomization. Algorithm D m can be considered as a greedy version of B m , whereas E m and F m are versions of local search algorithm, specialized for the k -matching problem. The algorithms are implemented in Python and are run on three datasets. On the datasets available, all the algorithms clearly outperform Algorithm A m in terms of solution quality. On the first dataset with known optimal values the average relative error ranges from 1.47% over optimum (algorithm A m ) to 0.08% over optimum (algorithm E m ). On the second dataset with known optimal values the average relative error ranges from 4.41% over optimum (algorithm A m ) to 0.45% over optimum (algorithm F m ). Better quality of solutions demands higher computation times, thus the new algorithms provide a good compromise between quality of solutions and computation time.

Keywords: k-assignment problem; k-matching problem; heuristic algorithm; local search; greedy algorithm; hungarian method (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/11/2050/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/11/2050/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:11:p:2050-:d:446526

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().