Multiple Hungarian method for k-assignment problem

Gabrovšek, Boštjan (author), Novak, Tina (author), Povh, Janez (author), Rupnik Poklukar, Darja (author), Žerovnik, Janez (author)

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.

• Language: English
• Keywords: k-assignment problem, k-matching problem, heuristic algorithm, local search, greedy algorithm, Hungarian method
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering; FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2020
• Number of pages: 18 str.
• Numbering: Vol. 8, iss. 11, art. 2050
• PID: 20.500.12556/RUL-122113
• UDC: 51(045)
• ISSN on article: 2227-7390
• DOI: 10.3390/math8112050
• COBISS.SI-ID: 38799875
• Publication date in RUL: 23.11.2020

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 17.11.2020

Secondary language

• Language: Slovenian
• Keywords: problem k-prirejanja, problem k-ujemanja, hevristični algoritem, lokalno iskanje, požrešni algoritem, madžarska metoda