-
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.Source: Mathematics [Elektronski vir]. - ISSN 2227-7390 (Vol. 8, iss. 11, Nov. 2020, f. 1-18)Type of material - e-articlePublish date - 2020Language - englishCOBISS.SI-ID - 38799875
Author
Gabrovšek, Boštjan, matematik, 1981- |
Novak, Tina, 1977- |
Povh, Janez, 1973- |
Rupnik Poklukar, Darja |
Žerovnik, Janez, 1958-
Topics
problem k-prirejanja |
problem k-ujemanja |
hevristični algoritem |
lokalno iskanje |
požrešni algoritem |
Madžarska metoda |
k-assignment problem |
k-matching problem |
heuristic algorithm |
local search |
greedy algorithm |
hungarian method
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Gabrovšek, Boštjan, matematik, 1981- | 29631 |
Novak, Tina, 1977- | 32686 |
Povh, Janez, 1973- | 22649 |
Rupnik Poklukar, Darja | 21774 |
Žerovnik, Janez, 1958- | 03430 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.