izpis_h1_title_alt

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

.pdfPDF - Presentation file, Download (3,73 MB)
MD5: F591E831E43F81635C0D19F50ED5962D
URLURL - Source URL, Visit https://www.mdpi.com/2227-7390/8/11/2050 This link opens in a new window

Abstract
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.

Language:English
Keywords:k-assignment problem, k-matching problem, heuristic algorithm, local search, greedy algorithm, Hungarian method
Work type:Article (dk_c)
Typology:1.01 - Original Scientific Article
Organization:FS - Faculty of Mechanical Engineering
FMF - Faculty of Mathematics and Physics
Year:2020
Publication status in journal:Published
Article version:Publisher's version of article
Number of pages:18 str.
Numbering:Vol. 8, iss. 11, art. 2050
UDC:51(045)
ISSN on article:2227-7390
DOI:10.3390/math8112050 This link opens in a new window
COBISS.SI-ID:38799875 This link opens in a new window
Publication date in RUL:23.11.2020
Views:396
Downloads:235
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Record is a part of a journal

Title:Mathematics
Shortened title:Mathematics
Publisher:MDPI
ISSN:2227-7390
COBISS.SI-ID:523267865 This link opens in a new window

Licences

License:CC BY 4.0, Creative Commons Attribution 4.0 International
Link:http://creativecommons.org/licenses/by/4.0/
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
Licensing start date:17.11.2020

Secondary language

Language:Slovenian
Keywords:problem k-prirejanja, problem k-ujemanja, hevristični algoritem, lokalno iskanje, požrešni algoritem, madžarska metoda

Document is financed by a project

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
izpis_stevilka_projekta:J1-8155
Name:Zlivanje biomedicinskih podatkov z uporabo nenegativne matrične tri-faktorizacije

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
izpis_stevilka_projekta:J1-1693
Name:Sodobni in novi metrični koncepti v teoriji grafov

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
izpis_stevilka_projekta:P2-0248
Name:Inovativni izdelovalni sistemi in procesi

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
izpis_stevilka_projekta:J2-2512
Name:Stohastični modeli za logistiko proizvodnih procesov

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

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back