Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods

Eden Chlamtac, Zac Friggstad, Konstantinos Georgiou

Recently, Cygan, Kowalik, and Wykurz [IPL 2009] gave sub-exponential-time approximation algorithms for the Set-Cover problem with approximation ratios better than ln(n). In light o…