An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality

•Improved approximation algorithm for TSP with relaxed triangle inequality.•Approximate Min. weight degree-4-bounded Eulerian subgraph of doubled complete graph.•Application of degree bounded matroids, b-matchings, and a new orientation technique.

Given a complete edge-weighted graph G, we present a polynomial time algorithm to compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G  . Based on this algorithm and a novel use of orientations in graphs, we obtain a (3β/4+3β2/4)(3β/4+3β2/4)-approximation algorithm for TSP with β-relaxed triangle inequality (β  -TSP), where β≥1β≥1. A graph G is an instance of β  -TSP, if it is a complete graph with edge weights c:E(G)→Q≥0c:E(G)→Q≥0 that are restricted as follows. For each triple of vertices u,v,w∈V(G)u,v,w∈V(G), c({u,v})≤β(c({u,w})+c({w,v}))c({u,v})≤β(c({u,w})+c({w,v})).