ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 5. Vol. 29. 2023

DOI: 10.17587/it.29.236-242

A. M. Sheveleva, PhD student, S. A. Belyaev, PhD, Assistant Professor,
Saint Petersburg Electrotechnical University, Saint Petersburg, 197022, Russian Federation

Phase Transitions in the Reduction of the Traveling Salesman Problem and the Two-Level Cooperative Assignment Problem

The paper considers algorithms for reducing the NP-hard traveling salesman problem to a two-level cooperative assignment problem and vice versa. The accuracy of the information of both algorithms is demonstrated by an example. Using the known conditions of the phase transition in the traveling salesman problem, copies of the problem were created, on which a computational experiment was subsequently carried out. The experiment is aimed at demonstrating the conservation of the phase transition when reducing one problem to another.
Keywords: traveling salesman problem, two-level cooperative assignment problem, reduction algorithms, phase transition

P. 236-242

References

1. Karp R. On the computational complexity of combinatorial problems, Networks, 1975, pp. 45—68.
2. Garey I . R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, San-Francisco, Freeman, 1979.
3. Cheeseman F., Kanefsky B., Taylor W. M. Where the really hard problems are, Proceedings NCAI-91, Sydney, 1975, pp. 331—337.
4. Gent I. P., Walsh T. The TSP phase transition, Artificial Intelligence, 1996, pp. 349—358.
5. Valkovsky V. B., Belyaev S. A. The use of phase transitions in the solution of combinatorial problems, Programmnye produkty i sistemy, 2000, no 4, pp. 37—38 (In Russian).
6. Valkovsky V. B., Belyaev S. A. Intelligent return under phase transition conditions for solving combinatorial problems, Programmnye produkty i sistemy, 2002, no. 4, pp. 16—19 (in Rus­sian).
7. Sharma P. C., Chaundhari N. Phase Transition in Reduc­tion between 3-SAT and Graph Colorability for Channel Assign­ment in Cellular Network, Conference: Computational Intelligence and Communication Networks (CICN), 2012.
8. Tsiatas A. Phase transitions in Boolean satisfiability and graph coloring, Department of Computer Science, Cornell University, 2008.
9. Sheveleva A. M., Belyaev S. A. Development of the Software for Solving the Knapsack Problem by Solving the Traveling Salesman Problem, IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus), 2021.
10. Sheveleva A. M., Razumovsky G. V. The design of the algorithm reduction of a binary cooperative assignment problem to a travelling salesman problem, Software Journal: Theory and Applications, 2020, no. 3.
11. Mudrov V. I. The Traveling Salesman Problem, Moscow, Znanie, 1969, 62 p. (In Russian).
12. Larin R. M., Paytkin A. B. Two-Level Assignment Problem, Diskretnyy analiz i issledovanie operaciy, 2001, no. 2, pp. 42—51 (In Russian).
13. Land A. H., Doig A. G. An Automatic Method of Solving Discrete Programming Problems, The Econometric Society, 1960, no. 3, pp. 497—520.
14. Belyaev S. A. The use of constraint technology in solving combinatorial optimization problems in conditions of phase transitions, diss. ... techn. PhD, 05.13.11. SPEU "LETI", Saint Peterburg, 2003, p 149 (In Russian).

To the contents