Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
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
)
PDF - Presentation file,
Download
(3,73 MB)
MD5: F591E831E43F81635C0D19F50ED5962D
URL - Source URL, Visit
https://www.mdpi.com/2227-7390/8/11/2050
Image galllery
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
Typology:
1.01 - Original Scientific Article
Organization:
FS - Faculty of Mechanical Engineering
FMF - Faculty of Mathematics and Physics
Publication status:
Published
Publication version:
Version of Record
Year:
2020
Number of pages:
18 str.
Numbering:
Vol. 8, iss. 11, art. 2050
PID:
20.500.12556/RUL-122113
UDC:
51(045)
ISSN on article:
2227-7390
DOI:
10.3390/math8112050
COBISS.SI-ID:
38799875
Publication date in RUL:
23.11.2020
Views:
2122
Downloads:
331
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Record is a part of a journal
Title:
Mathematics
Shortened title:
Mathematics
Publisher:
MDPI AG
ISSN:
2227-7390
COBISS.SI-ID:
523267865
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
Projects
Funder:
ARRS - Slovenian Research Agency
Project number:
J1-8155
Name:
Zlivanje biomedicinskih podatkov z uporabo nenegativne matrične tri-faktorizacije
Funder:
ARRS - Slovenian Research Agency
Project number:
J1-1693
Name:
Sodobni in novi metrični koncepti v teoriji grafov
Funder:
ARRS - Slovenian Research Agency
Project number:
P2-0248
Name:
Inovativni izdelovalni sistemi in procesi
Funder:
ARRS - Slovenian Research Agency
Project number:
J2-2512
Name:
Stohastični modeli za logistiko proizvodnih procesov
Funder:
ARRS - Slovenian Research Agency
Project number:
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