izpis_h1_title_alt

Multiple Hungarian method for k-assignment problem
ID Gabrovšek, Boštjan (Avtor), ID Novak, Tina (Avtor), ID Povh, Janez (Avtor), ID Rupnik Poklukar, Darja (Avtor), ID Žerovnik, Janez (Avtor)

.pdfPDF - Predstavitvena datoteka, prenos (3,73 MB)
MD5: F591E831E43F81635C0D19F50ED5962D
URLURL - Izvorni URL, za dostop obiščite https://www.mdpi.com/2227-7390/8/11/2050 Povezava se odpre v novem oknu

Izvleček
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 (dk_c)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FS - Fakulteta za strojništvo
FMF - Fakulteta za matematiko in fiziko
Leto izida:2020
Status objave pri reviji:Objavljeno
Verzija članka:Založnikova različica članka
Št. strani:18 str.
Številčenje:Vol. 8, iss. 11, art. 2050
UDK:51(045)
ISSN pri članku:2227-7390
DOI:10.3390/math8112050 Povezava se odpre v novem oknu
COBISS.SI-ID:38799875 Povezava se odpre v novem oknu
Datum objave v RUL:23.11.2020
Število ogledov:426
Število prenosov:238
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Gradivo je del revije

Naslov:Mathematics
Skrajšan naslov:Mathematics
Založnik:MDPI
ISSN:2227-7390
COBISS.SI-ID:523267865 Povezava se odpre v novem oknu

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

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:J1-8155
Naslov:Zlivanje biomedicinskih podatkov z uporabo nenegativne matrične tri-faktorizacije

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:J1-1693
Naslov:Sodobni in novi metrični koncepti v teoriji grafov

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:P2-0248
Naslov:Inovativni izdelovalni sistemi in procesi

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:J2-2512
Naslov:Stohastični modeli za logistiko proizvodnih procesov

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:N1-0071
Naslov:Razširitev algoritmov prvega in drugega reda za izbrane razrede optimizacijskih problemov s ciljem rešiti računsko zahtevne industrijske probleme

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj