The Symmetric Travelling Salesman Problem I. New Fast Lower Bounds for the Problem of Optimal 2-Matching

摘要

To solve the symmetric travelling salesman problem we suggest a lower bound-the solution of an optimal 2-matching problem. The latter problem is solved (in a polynomial number of steps) not completely, but up to obtaining new stable lower bounds.