I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture.

The Held-Karp relaxation is conjectured to have an integrality gap of $\frac{4}{3}$ for symmetric TSP.

There have been some recent advances in proving this conjecture. Among these include the 4/3 conjecture for metric TSP was proved for cubic and subcubic graphs by Boyd et. al. http://arxiv.org/pdf/1107.1052v1.pdf.

Furthermore, for the class of graphs that are degree-3 bounded and are claw-free, the Held-Karp relaxation yields a 4/3 approximation ratio as proven by Momke et. al. : http://arxiv.org/abs/1104.3090.

Then, Qian et.al. (http://arxiv.org/abs/1107.1630) proved that for a special case of graphs with all edges have cost $1$ or $2$, there exists a bound of 10/9.

I would very much appreciate if anyone with more expertise in this research topic would point out other recent research advances in proving the Held-Karp conjecture. Links and/or titles to research papers would be very helpful.

  • $\begingroup$ One somehow great improvement on recent results is 13/9 approximation for graphic TSP, I don't know if there is any newer improvement but you can check it by google citation. $\endgroup$
    – Saeed
    Nov 17, 2014 at 16:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.