Multiple Hungarian Method for <i>k</i>-Assignment Problem
The <i>k</i>-assignment problem (or, the <i>k</i>-matching problem) on <i>k</i>-partite graphs is an NP-hard problem for <inline-formula><math display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/11/2050 |
| _version_ | 1797547627114397696 |
|---|---|
| author | Boštjan Gabrovšek Tina Novak Janez Povh Darja Rupnik Poklukar Janez Žerovnik |
| author_facet | Boštjan Gabrovšek Tina Novak Janez Povh Darja Rupnik Poklukar Janez Žerovnik |
| author_sort | Boštjan Gabrovšek |
| collection | DOAJ |
| description | The <i>k</i>-assignment problem (or, the <i>k</i>-matching problem) on <i>k</i>-partite graphs is an NP-hard problem for <inline-formula><math display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula>. In this paper we introduce five new heuristics. Two algorithms, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">B</mi><mi>m</mi></msub></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">C</mi><mi>m</mi></msub></semantics></math></inline-formula>, arise as natural improvements of Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula> from (He et al., in: Graph Algorithms And Applications 2, World Scientific, 2004). The other three algorithms, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">D</mi><mi>m</mi></msub></semantics></math></inline-formula>, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula>, and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula>, incorporate randomization. Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">D</mi><mi>m</mi></msub></semantics></math></inline-formula> can be considered as a greedy version of <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">B</mi><mi>m</mi></msub></semantics></math></inline-formula>, whereas <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula> are versions of local search algorithm, specialized for the <i>k</i>-matching problem. The algorithms are implemented in Python and are run on three datasets. On the datasets available, all the algorithms clearly outperform Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula> in terms of solution quality. On the first dataset with known optimal values the average relative error ranges from 1.47% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula>) to 0.08% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula>). On the second dataset with known optimal values the average relative error ranges from 4.41% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula>) to 0.45% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula>). Better quality of solutions demands higher computation times, thus the new algorithms provide a good compromise between quality of solutions and computation time. |
| first_indexed | 2024-03-10T14:46:45Z |
| format | Article |
| id | doaj.art-6285a8cf440d4079bb5daa0f3a4d4ae1 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T14:46:45Z |
| publishDate | 2020-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-6285a8cf440d4079bb5daa0f3a4d4ae12023-11-20T21:17:12ZengMDPI AGMathematics2227-73902020-11-01811205010.3390/math8112050Multiple Hungarian Method for <i>k</i>-Assignment ProblemBoštjan Gabrovšek0Tina Novak1Janez Povh2Darja Rupnik Poklukar3Janez Žerovnik4Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, SloveniaFaculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, SloveniaFaculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, SloveniaFaculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, SloveniaFaculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, SloveniaThe <i>k</i>-assignment problem (or, the <i>k</i>-matching problem) on <i>k</i>-partite graphs is an NP-hard problem for <inline-formula><math display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula>. In this paper we introduce five new heuristics. Two algorithms, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">B</mi><mi>m</mi></msub></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">C</mi><mi>m</mi></msub></semantics></math></inline-formula>, arise as natural improvements of Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula> from (He et al., in: Graph Algorithms And Applications 2, World Scientific, 2004). The other three algorithms, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">D</mi><mi>m</mi></msub></semantics></math></inline-formula>, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula>, and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula>, incorporate randomization. Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">D</mi><mi>m</mi></msub></semantics></math></inline-formula> can be considered as a greedy version of <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">B</mi><mi>m</mi></msub></semantics></math></inline-formula>, whereas <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula> are versions of local search algorithm, specialized for the <i>k</i>-matching problem. The algorithms are implemented in Python and are run on three datasets. On the datasets available, all the algorithms clearly outperform Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula> in terms of solution quality. On the first dataset with known optimal values the average relative error ranges from 1.47% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula>) to 0.08% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula>). On the second dataset with known optimal values the average relative error ranges from 4.41% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula>) to 0.45% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula>). Better quality of solutions demands higher computation times, thus the new algorithms provide a good compromise between quality of solutions and computation time.https://www.mdpi.com/2227-7390/8/11/2050k-assignment problemk-matching problemheuristic algorithmlocal searchgreedy algorithmhungarian method |
| spellingShingle | Boštjan Gabrovšek Tina Novak Janez Povh Darja Rupnik Poklukar Janez Žerovnik Multiple Hungarian Method for <i>k</i>-Assignment Problem Mathematics k-assignment problem k-matching problem heuristic algorithm local search greedy algorithm hungarian method |
| title | Multiple Hungarian Method for <i>k</i>-Assignment Problem |
| title_full | Multiple Hungarian Method for <i>k</i>-Assignment Problem |
| title_fullStr | Multiple Hungarian Method for <i>k</i>-Assignment Problem |
| title_full_unstemmed | Multiple Hungarian Method for <i>k</i>-Assignment Problem |
| title_short | Multiple Hungarian Method for <i>k</i>-Assignment Problem |
| title_sort | multiple hungarian method for i k i assignment problem |
| topic | k-assignment problem k-matching problem heuristic algorithm local search greedy algorithm hungarian method |
| url | https://www.mdpi.com/2227-7390/8/11/2050 |
| work_keys_str_mv | AT bostjangabrovsek multiplehungarianmethodforikiassignmentproblem AT tinanovak multiplehungarianmethodforikiassignmentproblem AT janezpovh multiplehungarianmethodforikiassignmentproblem AT darjarupnikpoklukar multiplehungarianmethodforikiassignmentproblem AT janezzerovnik multiplehungarianmethodforikiassignmentproblem |