Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm
In this paper, we consider the notion of a direct type algorithm introduced by V. A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properties. the concept of a direct type algorithm is determined using the graph of solutions of a combinatorial optimization p...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2020-03-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1289 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849688278602612736 |
|---|---|
| author | Aleksandr N. Maksimenko |
| author_facet | Aleksandr N. Maksimenko |
| author_sort | Aleksandr N. Maksimenko |
| collection | DOAJ |
| description | In this paper, we consider the notion of a direct type algorithm introduced by V. A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properties. the concept of a direct type algorithm is determined using the graph of solutions of a combinatorial optimization problem. e vertices of this graph are all feasible solutions of a problem. Two solutions are called adjacent if there are input data for which these and only these solutions are optimal. A key feature of direct type algorithms is that their complexity is bounded from below by the clique number of the solutions graph. In 2015-2018, there were five papers published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. the main motivation in these works is the thesis that the class of direct type algorithms is wide and includes many classical combinatorial algorithms, including the branch and bound algorithm for the traveling salesman problem, proposed by J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel in 1963. We show that this algorithm is not a direct type algorithm. Earlier, in 2014, the author of this paper showed that the Hungarian algorithm for the assignment problem is not a direct type algorithm. us, the class of direct type algorithms is not so wide as previously assumed. |
| format | Article |
| id | doaj-art-224d9349b9b34e469fa33eb2ffeb0ad3 |
| institution | DOAJ |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2020-03-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-224d9349b9b34e469fa33eb2ffeb0ad32025-08-20T03:22:03ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172020-03-01271728510.18255/1818-1015-2020-1-72-85960Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type AlgorithmAleksandr N. Maksimenko0P. G. Demidov Yaroslavl State UniversityIn this paper, we consider the notion of a direct type algorithm introduced by V. A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properties. the concept of a direct type algorithm is determined using the graph of solutions of a combinatorial optimization problem. e vertices of this graph are all feasible solutions of a problem. Two solutions are called adjacent if there are input data for which these and only these solutions are optimal. A key feature of direct type algorithms is that their complexity is bounded from below by the clique number of the solutions graph. In 2015-2018, there were five papers published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. the main motivation in these works is the thesis that the class of direct type algorithms is wide and includes many classical combinatorial algorithms, including the branch and bound algorithm for the traveling salesman problem, proposed by J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel in 1963. We show that this algorithm is not a direct type algorithm. Earlier, in 2014, the author of this paper showed that the Hungarian algorithm for the assignment problem is not a direct type algorithm. us, the class of direct type algorithms is not so wide as previously assumed.https://www.mais-journal.ru/jour/article/view/1289branch and boundtraveling salesman problemlinear decision treeclique numberdirect type algorithm |
| spellingShingle | Aleksandr N. Maksimenko Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm Моделирование и анализ информационных систем branch and bound traveling salesman problem linear decision tree clique number direct type algorithm |
| title | Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm |
| title_full | Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm |
| title_fullStr | Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm |
| title_full_unstemmed | Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm |
| title_short | Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm |
| title_sort | branch and bound algorithm for the traveling salesman problem is not a direct type algorithm |
| topic | branch and bound traveling salesman problem linear decision tree clique number direct type algorithm |
| url | https://www.mais-journal.ru/jour/article/view/1289 |
| work_keys_str_mv | AT aleksandrnmaksimenko branchandboundalgorithmforthetravelingsalesmanproblemisnotadirecttypealgorithm |