Complexity of Solutions Combination for the Three-Index Axial Assignment Problem
In this work we consider the NP-hard three-index axial assignment problem. We formulate and investigate a problem of combining feasible solutions. Such combination can be applied in a wide range of heuristic and approximate algorithms for solving the assignment problem, instead of the commonly used...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/7/1062 |
| _version_ | 1797438525026598912 |
|---|---|
| author | Lev G. Afraimovich Maxim D. Emelin |
| author_facet | Lev G. Afraimovich Maxim D. Emelin |
| author_sort | Lev G. Afraimovich |
| collection | DOAJ |
| description | In this work we consider the NP-hard three-index axial assignment problem. We formulate and investigate a problem of combining feasible solutions. Such combination can be applied in a wide range of heuristic and approximate algorithms for solving the assignment problem, instead of the commonly used strategy of selecting the best solution among the found feasible solutions. We discuss approaches to a solution of the combination problem and prove that it becomes NP-hard already in the case of combining four solutions. |
| first_indexed | 2024-03-09T11:39:13Z |
| format | Article |
| id | doaj.art-6b1d9afac05749fab973fc6a9b8b5c31 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T11:39:13Z |
| publishDate | 2022-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-6b1d9afac05749fab973fc6a9b8b5c312023-11-30T23:36:35ZengMDPI AGMathematics2227-73902022-03-01107106210.3390/math10071062Complexity of Solutions Combination for the Three-Index Axial Assignment ProblemLev G. Afraimovich0Maxim D. Emelin1Institute of Information Technology, Mathematics and Mechanics, Lobachevsky State University of Nizhny Novgorod, Nizhny Novgorod 603022, RussiaInstitute of Information Technology, Mathematics and Mechanics, Lobachevsky State University of Nizhny Novgorod, Nizhny Novgorod 603022, RussiaIn this work we consider the NP-hard three-index axial assignment problem. We formulate and investigate a problem of combining feasible solutions. Such combination can be applied in a wide range of heuristic and approximate algorithms for solving the assignment problem, instead of the commonly used strategy of selecting the best solution among the found feasible solutions. We discuss approaches to a solution of the combination problem and prove that it becomes NP-hard already in the case of combining four solutions.https://www.mdpi.com/2227-7390/10/7/1062axial assignment problemmulti-index problemapproximate algorithmsNP-hardness |
| spellingShingle | Lev G. Afraimovich Maxim D. Emelin Complexity of Solutions Combination for the Three-Index Axial Assignment Problem Mathematics axial assignment problem multi-index problem approximate algorithms NP-hardness |
| title | Complexity of Solutions Combination for the Three-Index Axial Assignment Problem |
| title_full | Complexity of Solutions Combination for the Three-Index Axial Assignment Problem |
| title_fullStr | Complexity of Solutions Combination for the Three-Index Axial Assignment Problem |
| title_full_unstemmed | Complexity of Solutions Combination for the Three-Index Axial Assignment Problem |
| title_short | Complexity of Solutions Combination for the Three-Index Axial Assignment Problem |
| title_sort | complexity of solutions combination for the three index axial assignment problem |
| topic | axial assignment problem multi-index problem approximate algorithms NP-hardness |
| url | https://www.mdpi.com/2227-7390/10/7/1062 |
| work_keys_str_mv | AT levgafraimovich complexityofsolutionscombinationforthethreeindexaxialassignmentproblem AT maximdemelin complexityofsolutionscombinationforthethreeindexaxialassignmentproblem |