Multiple Hungarian method for k-assignment problemGabrovšek, Boštjan (Avtor) Novak, Tina (Avtor) Povh, Janez (Avtor) Rupnik Poklukar, Darja (Avtor) Žerovnik, Janez (Avtor) k-assignment problemk-matching problemheuristic algorithmlocal searchgreedy algorithmHungarian methodThe 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.20202020-11-23 10:48:38Članek v reviji122113UDK: 51(045)ISSN pri članku: 2227-7390DOI: 10.3390/math8112050COBISS_ID: 38799875sl