1
$\begingroup$

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?

$\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$ Jun 7, 2023 at 9:34
  • 1
    $\begingroup$ You may want to see Section 2 of this paper as well. $\endgroup$ Jun 7, 2023 at 10:04
  • $\begingroup$ @InuyashaYagami I wonder if it is possible to get an approximation factor of 3c/2 $\endgroup$ 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$ Jun 7, 2023 at 12:57

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.