Multiple Hungarian method for k-assignment problem

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

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.

• Jezik: Angleški jezik
• Ključne besede: k-assignment problem, k-matching problem, heuristic algorithm, local search, greedy algorithm, Hungarian method
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FS - Fakulteta za strojništvo ; FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2020
• Št. strani: 18 str.
• Številčenje: Vol. 8, iss. 11, art. 2050
• PID: 20.500.12556/RUL-122113
• UDK: 51(045)
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math8112050
• COBISS.SI-ID: 38799875
• Datum objave v RUL: 23.11.2020

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 17.11.2020

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: problem k-prirejanja, problem k-ujemanja, hevristični algoritem, lokalno iskanje, požrešni algoritem, madžarska metoda