Exponential-time approximation of weighted set cover

The Set Cover problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. In recent years, many researchers design exact exponential-time algorithms for problems of that kind. The goal is getting the time complexity still of order O(cn), but with the constant c as small as possible. In this work we extend this line of research and we investigate whether the constant c can be made even smaller when one allows constant factor approximation.In fact, we describe a kind of approximation schemes—trade-offs between approximation factor and the time complexity. We use general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate r, one can transform any O∗(cn)-time1 algorithm for Set Cover into a (1+lnr)-approximation algorithm running in time O∗(cn/r). We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems.