The traveling salesman problem with distances one and two. (English) Zbl 0778.90057

Proposed is a polynomial-time approximation algorithm for the solution of the traveling salesman problem with worst-case ratio 7/6 in graphs in which the weights on edges equal 1 or 2. Previous results for weighted graphs with weights on edges satisfying the triangle inequality had ratio 3/2. The presented procedure uses the technique of subtour patching and several theorems prove that due to the particularity of the considered graphs with distance values of 1 or 2 the worst-case ratio is 7/6.


90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
90C35 Programming involving graphs or networks
90C10 Integer programming
Full Text: DOI