Thursday, April 29, 2010

On the Intergrality ratio of Assymetric travelling salesman problem

[@ 3:30pm. 29 April, 2010. SIC 305, KReSIT]
Sagar Kale

Toy problem: TODO.

We( Moses Charikar , Michel X. Goemans , Howard Karloff) improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP with triangle inequality from 4/3 to 2.

No comments:

Post a Comment