-
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-članekLeto - 2020Jezik - angleškiCOBISS.SI-ID - 38799875
Avtor
Gabrovšek, Boštjan, matematik, 1981- |
Novak, Tina, 1977- |
Povh, Janez, 1973- |
Rupnik Poklukar, Darja |
Žerovnik, Janez, 1958-
Teme
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
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Gabrovšek, Boštjan, matematik, 1981- | 29631 |
Novak, Tina, 1977- | 32686 |
Povh, Janez, 1973- | 22649 |
Rupnik Poklukar, Darja | 21774 |
Žerovnik, Janez, 1958- | 03430 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.