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.
Reviewer: V.O.Groppen (Vladikaukaz)
MSC:
90C27 | Combinatorial optimization |
90C60 | Abstract computational complexity for mathematical programming problems |
90C35 | Programming involving graphs or networks |
90C10 | Integer programming |