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

Papadimitriou, Christos H.; Yannakakis, Mihalis

Math. Oper. Res. 18, No. 1, 1-11 (1993).

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

Keywords:

polynomial-time approximation algorithm; traveling salesman; weighted graphs; subtour patching