Complexity of Solutions Combination for the Three-Index Axial Assignment Problem

Lev G. Afraimovich and Maxim D. Emelin
Additional contact information
Lev G. Afraimovich: Institute of Information Technology, Mathematics and Mechanics, Lobachevsky State University of Nizhny Novgorod, Nizhny Novgorod 603022, Russia
Maxim D. Emelin: Institute of Information Technology, Mathematics and Mechanics, Lobachevsky State University of Nizhny Novgorod, Nizhny Novgorod 603022, Russia

Mathematics, 2022, vol. 10, issue 7, 1-10

Abstract: 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.

Keywords: axial assignment problem; multi-index problem; approximate algorithms; NP-hardness (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/7/1062/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/7/1062/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:7:p:1062-:d:779720

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().