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

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

2012-04-24

arxiv.org/abs/1204.5489v1

Mathematics

Combinatorics

Scientific paper

We study sub-exponential time approximation algorithms for the Set-Cover problem. Our main algorithmic result is a combinatorial ln(n/d)+O(1) approximation in poly(n,m)*m^O(d) time, where n is the number of items to be covered and m is the number of sets. Setting d = n^eps for any constant 0 < eps < 1 results in a (1-eps)*ln n approximation running in sub-exponential time. By recent work of Moshkovitz, assuming the Projection Games Conjecture, the running time of our algorithm is optimal up to a constant factor in the exponent of n, unless SAT has sub-exponential time algorithms. At a high level, our algorithm is similar to a well-known PTAS for Knapsack. Recently, Karlin, Mathieu, and Nguyen examined this PTAS and its connection to hierarchies of linear programming (LP) and semidefinite programing (SDP) relaxations for Knapsack. Inspired by their work, we also consider the integrality gap of Set-Cover relaxations arising from such hierarchies. We show that, using the trick of "lifting the objective function", we can match the performance of our combinatorial Set-Cover algorithm using the LP hierarchy of Lovasz and Schrijver. We also show that this trick is essential: even in the stronger LP hierarchy of Sherali and Adams, the integrality gap remains at least (1-eps)*ln n at level Omega(n) (when the objective function is not lifted). As shown by Aleknovich, Arora, and Tourlakis, Set-Cover relaxations stemming from SDP hierarchies (specifically, LS_+) have similarly large integrality gaps. This stands in contrast to Knapsack, where Karlin et al. showed that the (much stronger) Lasserre SDP hierarchy reduces the integrality gap to (1+eps) at level O(1). For completeness, we show that LS_+ also reduces the integrality gap for Knapsack to (1+eps). This result may be of independent interest, as our LS_+-based rounding and analysis are rather different from those of Karlin et al.

Affiliated with

Also associated with

No associations

Rating

Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-136925