20.500.12556/RUL-122113 Multiple Hungarian method for k-assignment problem 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. k-assignment problem k-matching problem heuristic algorithm local search greedy algorithm Hungarian method problem k-prirejanja problem k-ujemanja hevristični algoritem lokalno iskanje požrešni algoritem madžarska metoda true false true Angleški jezik Slovenski jezik Članek v reviji 2020-11-23 10:48:38 2020-11-23 10:48:43 2022-09-02 04:02:26 0000-00-00 00:00:00 2020 0 0 18 str. iss. 11, art. 2050 Vol. 8 Nov. 2020 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(045) 2227-7390 10.3390/math8112050 38799875 RAZ_Gabrovsek_Bostjan_2020.pdf RAZ_Gabrovsek_Bostjan_2020.pdf 1 F591E831E43F81635C0D19F50ED5962D 3b86aba4954aabf4653924f8717d58f7e0d739f3e4844c03d22468987760b6ea 039844d7-8028-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=153357 https://www.mdpi.com/2227-7390/8/11/2050 1 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=137276 Fakulteta za strojništvo Fakulteta za matematiko in fiziko 0 0 0