  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 of this result, it is natural to ask whether such
improvements can be achieved using lift-and-project methods. We present a
simpler combinatorial algorithm which has nearly the same time-approximation
tradeoff as the algorithm of Cygan et al., and which lends itself naturally to
a lift-and-project based approach.
  At a high level, our approach is similar to the recent work of Karlin,
Mathieu, and Nguyen [IPCO 2011], who examined a known PTAS for Knapsack
(similar to our combinatorial Set-Cover algorithm) and its connection to
hierarchies of LP and SDP relaxations for Knapsack. For Set-Cover, we show
that, indeed, using the trick of "lifting the objective function", we can match
the performance of our combinatorial 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 [STOC 2005], 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., and to the best of our knowledge this is
the first explicit demonstration of such a reduction in the integrality gap of
LS+ relaxations after few rounds.
