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

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