Zhurovskyy M., Pavlov A.

In this paper we research the properties of one of the most well-known NP-hard in the strong sense problems of combinatorial optimization. We formulate and substantiate the statements to construct the PSС-algorithm for its solving: sufficient signs of optimality of the obtained solutions, conditions for excluding competing tasks, and rules for cutting off unpromising permutations. We show properties of the polynomial and exponential components of the PSC-algorithm, prove its finiteness and optimality.

Download (pdf)