[@ 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