Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа
https://doi.org/10.18255/1818-1015-2020-1-72-85
Аннотация
Ключевые слова
MSC2020: 90C57
Об авторе
Александр Николаевич МаксименкоРоссия
канд. физ.-мат. наук, доцент
Список литературы
1. V. Bondarenko, A. Nikolaev, and D. Shovgenov, “1-skeletons of the spanning tree problems with additional constraints”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 682–688, 2017.
2. V. Bondarenko and A. Nikolaev, “On graphs of the cone decompositions for the min-cut and max-cut problems”, International Journal of Mathematics and Mathematical Sciences, vol. 2016, 2016.
3. V. Bondarenko and A. Nikolaev, “Some properties of the skeleton of the pyramidal tours polytope”, Electronic Notes in Discrete Mathematics, vol. 61, pp. 131–137, 2017.
4. V. A. Bondarenko, A. V. Nikolaev, and D. Shovgenov, “Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 576–585, 2017.
5. V. Bondarenko and A. Nikolaev, “On the skeleton of the polytope of pyramidal tours”, Journal of Applied and Industrial Mathematics, vol. 12, no. 1, pp. 9–18, 2018.
6. V. Bondarenko, “Nonpolynomial lowerbound of the traveling salesman problem complexity in one class of algorithms”, Automation and Remote Control, vol. 44, no. 9, pp. 1137–1142, 1983.
7. V. Bondarenko, “Geometricheskie metody sistemnogo analiza v kombinatornoy optimizatsii”, diss. ... dokt.fiz.-mat. nauk, Yaroslavl, 1993.
8. V. Bondarenko and A. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moskva: URSS, 2008, 182 pp.
9. A. Maksimenko, “Kharakteristiki slozhnosti: klikovoe chislo grafa mnogogrannika i chislo pryamougolnogo pokrytiya”, Modelirovanie i analiz informatsionnykh sistem, vol. 21, no. 5, pp. 116–130, 2014.
10. J. Little, K. Murty, D. Sweeney, and C. Karel, “An algorithm for the traveling salesman problem”, Operations research, vol. 11, no. 6, pp. 972–989, 1963.
11. E. Reingold, J. Nievergelt, and N. Deo, Combinatorial algorithms: theory and practice. Pearson College Div, 1977, 433 pp.
12. M. Padberg and M. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Mathematical Programming, vol. 7, no. 1, pp. 32–45, 1974.
Рецензия
Для цитирования:
Максименко А.Н. Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа. Моделирование и анализ информационных систем. 2020;27(1):72-85. https://doi.org/10.18255/1818-1015-2020-1-72-85
For citation:
Maksimenko A.N. Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm. Modeling and Analysis of Information Systems. 2020;27(1):72-85. (In Russ.) https://doi.org/10.18255/1818-1015-2020-1-72-85