The symmetric travelling salesman problem II. New low bounds

The branch-and-bound method is adduced for the symmetric salesman problem where two lower bounds are proposed as bounds. The first bound is a solution to the problem of optimal $2$-matching; the second one, to the problem of minimum spanning $1$-tree. The last bound is enhanced by applying the problem of optimal $2$-matching. Both these bounds considerably improve the symmetric traveling salesman problem as compared to the asymmetric problem.

Presented by the member of Editorial Board: A. A. Lazarev