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.

Approximation algorithm for facility location

[@ 3:30pm. 29 April, 2010. SIC 305, KReSIT]
Srinivas Karthik

The first approximation algorithm with a constant performance guarantee for the (metric) uncapacitated facility problem was given by Shmoys, Tardos, & Aardal. Their algorithm is an LP rounding algorithm with performance guarantee equal to 3/(1 - e^{-3}) = 3.16

Link to paper.