A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem

Abstract

In this paper, we consider differential approximability of the traveling salesman problem (TSP). We show that TSP is $3/4$-differential approximable, which improves the currently best known bound $3/4-O(1/n)$ due to Escoffier and Monnot in 2008, where $n$ denotes the number of vertices in the given graph.