# Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality

It is known that Christofides’ algorithm returns a 3/2-approximation for the traveling salesman problem given a complete graph $$G$$ such that distances obey the triangle inequality. Suppose that we weaken the triangle inequality to the setting where distances obey the guarantee that for each triple $$i, j, l \in V$$ it is the case that $$d_{ij} + d_{jl} \geq d_{il}/c$$ where $$c \geq 1$$. How do I then express the approximation ratio in terms of $$c$$? To do this, I think I have to find the cost of the shortcutted tour of $$G$$ that visits each node in the set of nodes with odd degree $$O$$. I know that if the distance just obeyed the normal triangle inequality, then this shortcut tour on $$O$$ would at most be the cost of the whole tour of $$G$$. But what is the cost when distances only obey the relaxed triangle inequality?

• I think the approximation guarantee can blow to $O(c^{\log n})$ for Christofides algorithm, where $n$ are number of vertices in the graph. Obtaining it is easy. Are you looking for a better guarantee? Jun 7, 2023 at 9:34
• You may want to see Section 2 of this paper as well. Jun 7, 2023 at 10:04
• @InuyashaYagami I wonder if it is possible to get an approximation factor of 3c/2 Jun 7, 2023 at 12:11
• That is an open problem. This is one of the recent paper that studies this problem. Jun 7, 2023 at 12:57