Approximation Algorithm for Travelling Salesman Problem

Abstract

Designing approximation algorithms often involves, among other things, relaxing the integrality constraint and obtaining a convex relaxation of the problem. The most well-known relaxation schemes are the Linear Programming (LP) relaxation and Semi-Definite Programing (SDP) relaxation. While LP relaxation has been widely used for solving TSP, SDP has been rarely employed. The primary goal of this paper therefore is to employ SDP and develop approximation algorithm for metric TSP. The SDP relaxation of the TSP is first obtained, and the approximation algorithm is thereafter developed. When compared to optimal results of some standard TSP instances, implementation result showed a relatively fair performance.