Approximation Algorithms for the Undirected Travelling Salesman Problem

Completed by: Aleksandar Markovic

Final report

We present an overview of known approximation algorithms and linear programming relaxations of the Undirected Travelling Salesman Problem with the triangle inequality.

In particular, we review the classical algorithm by Christofides and explain how it upper bounds the integrality gap of the considered linear programming relaxation.

We also complement this by presenting better upper bounds for specific cases, such as subcubic graphs in the unweighed shortest path metric and two 5-cycles connected by five paths in a general metric.