I know the double tree algorithm and Christofides algorithm with 1.5 approximation ratio. We got this question from the teacher.

  • $\begingroup$ Just to clarify, your teacher asked if there is a 3-approximation algorithm for TSP? What definition of an $\alpha$-approximation algorithm are you using? By the standard definition, if $\beta \leq \alpha$ then any $\beta$-approximation algorithm is also an $\beta$-approximation algorithm. $\endgroup$ Commented Jan 25 at 19:17
  • 1
    $\begingroup$ Do you know more about the class of instances, e.g. is it metric? $\endgroup$
    – Pål GD
    Commented Jan 25 at 19:22


Your Answer

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

Browse other questions tagged or ask your own question.