DIKUL - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Multiple Hungarian method for k-assignment problem [Elektronski vir]
    Gabrovšek, Boštjan, matematik, 1981- ...
    The k-assignment problem (or, the k-matching problem) on k-partite graphs is an NP-hard problem for k [greater than or equal to] 3. In this paper we introduce five new heuristics. Two algorithms, Bm ... and Cm, arise as natural improvements of Algorithm Am from (He et al., in: Graph Algorithms And Applications 2,World Scientific, 2004). The other three algorithms, Dm, Em, and Fm, incorporate randomization. Algorithm Dm can be considered as a greedy version of Bm, whereas Em and Fm 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 Am in terms of solution quality. On the first dataset with known optimal values the average relative error ranges from 1.47% over optimum (algorithm Am) to 0.08% over optimum (algorithm Em). On the second dataset with known optimal values the average relative error ranges from 4.41% over optimum (algorithm Am) to 0.45% over optimum (algorithm Fm). Better quality of solutions demands higher computation times, thus the new algorithms provide a good compromise between quality of solutions and computation time.
    Vir: Mathematics [Elektronski vir]. - ISSN 2227-7390 (Vol. 8, iss. 11, Nov. 2020, f. 1-18)
    Vrsta gradiva - e-članek
    Leto - 2020
    Jezik - angleški
    COBISS.SI-ID - 38799875

    Povezava(-e):

    https://www.mdpi.com/2227-7390/8/11/2050
    Repozitorij Univerze v Ljubljani – RUL
    DOI

Vnos na polico