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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ 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? $\endgroup$– Inuyasha YagamiCommented Jun 7, 2023 at 9:34
-
1$\begingroup$ You may want to see Section 2 of this paper as well. $\endgroup$– Inuyasha YagamiCommented Jun 7, 2023 at 10:04
-
$\begingroup$ @InuyashaYagami I wonder if it is possible to get an approximation factor of 3c/2 $\endgroup$– TheCollegeStudentCommented Jun 7, 2023 at 12:11
-
2$\begingroup$ That is an open problem. This is one of the recent paper that studies this problem. $\endgroup$– Inuyasha YagamiCommented Jun 7, 2023 at 12:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It is possible to get a bound of OPT + 0.5C * OPT assuming that the cost of the MST is less or equal than OPT and that the cost of the perfect matching is at most 0.5C * OPT which can done by constructing a tour in the set of odd degree vertices by shortcutting the general optimal tour.
