Improving Christofides' lower bound for the traveling salesman problem

Abstract

In 1972 Christofides introduced a lower bound for the Traveling Salesman Problem (TSP). The bound is based on solving repeatedly a Linear Assignment Problem. We relate the bound to the Complete Cycle Problem; as a consequence the correctness of the bound is easier to prove.

Further we give improvements for the bound in the symmetric case and we deal with the influence of the triangle equation together with the identification of non-optimal edges for the TSP. The improvements are illustrated by examples and computational results for large problems.

Keywords:

• Traveling Salesman Problem
• lower bound

AMS 1980 Subject Classifications:

• Primary: 94 C 15
• Secondary: 05 C 35