This article is cited in 1 paper

Optimization, System Analysis, and Operations Research

Criteria convolutions when combining the solutions of the multicriteria axial assignment problem

L. G. Afraimovich^a, M. D. Emelin<sup>b

a</sup> Lobachevski State University of Nizhni Novgorod
^b National Research Lobachevsky State University of Nizhny Novgorod

Abstract: This paper is devoted to a classical NP-hard problem, known as the three-index axial assignment problem. Within the corresponding framework, the problem of combining feasible solutions is posed as an assignment problem on the set of solutions containing only the components of selected feasible solutions. The issues of combining solutions for the multicriteria problem with different criteria convolutions are studied. In the general case, the combination problem turns out to be NP-hard. Polynomial solvability conditions are obtained for the combination problem.

Keywords: axial assignment problem, multi-index problems, combining solutions, polynomial solvability, NP-hardness.

Presented by the member of Editorial Board: A. A. Lazarev

Received: 04.03.2024
Revised: 21.05.2024
Accepted: 27.06.2024

DOI: 10.31857/S0005231024080063

 English version: Automation and Remote Control, 2024, 85:8, 718–726