Thursday, April 29, 2010

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.

No comments:

Post a Comment