Software Journal:
Theory and Applications

Send article

Entrance Registration

The design of the algorithm reduction of a binary cooperative assignment problem to a travelling salesman problem

A.M. Sheveleva St. Petersburg Electrotechnical University "LETI", Saint Petersburg, Russian Federation;
G.V. Razumovsky St. Petersburg Electrotechnical University "LETI", Saint Petersburg, Russian Federation;

The paper considers the pressing problem of reducing some NP-complete problems to others. The primary focus in this paper is the design of the algorithm reduction of a binary cooperative assignment problem to a travelling salesman problem to find its solution and transfer the solving performance of one NP-complete problem to another; there are brief mathematical formulations of the problems.

The paper describes the problems associated with reducing some NP-complete problems to others. As a sample, we consider an example of reducing the traveling salesman problem to the problem of the Hamiltonian cycle. The authors propose a new algorithm for reducing a binary cooperative assignment problem to a travelling salesman problem, which solves the current reduction problems that impose constraints on the NP-complete problems themselves.

The authors investigate the developed algorithm for reducing the accuracy of obtaining the result of the original NP-complete problem and the computational complexity.

The paper mathematically proves that the reduction algorithm does not reduce the accuracy of obtaining a solution to the binary cooperative assignment problem when the salesman problem is accurately solved. There are no restrictions on the problems themselves. The paper contains a mathematical argument for the polynomial computational complexity of the developed reduction algorithm.

For software demonstration of the correct operation, the developed reduction algorithm was implemented in the Java programming language, as well as exact algorithms for solving the binary cooperative assignment problem and the traveling salesman problem.

In this program, experiments were performed to find solutions to the original NP-complete problem with different amounts of input data, and the correctness of the reduction algorithm was confirmed.

The paper describes future trends for the analysis of this area.