# Hardness of approximation statement clarification?

In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved this problem considered in the paper with an approximation ratio less than or equal to $$(1 - \alpha)( 1 + \log x)$$ for any $$\alpha > 0$$, the result for set cover would be contradicted. $$x$$ is a quantity that is shown to satisfy $$x \leq n$$. The set cover result is that set cover is NP-hard to approximate within $$(1 - \alpha) \log n$$.

My confusion stems from the fact that $$(1 - \alpha)( 1 + \log x) \leq (1 - \alpha)( 1 + \log n)$$ is not less than $$(1 - \alpha) \log n$$.

Can we just disregard this constant additive factor of $$(1 - \alpha)$$? What if the approximation ratio had a constant multiplicative factor? Like it would something like $$(1 - \alpha)( 1 + \log x) (1 + \beta)$$, where $$\beta > 0$$?

## 1 Answer

Since $$1 + \log n = (1 + o(1)) \log n$$, for every $$\beta < \alpha$$ you can find $$N$$ such that for $$n \geq N$$, $$(1-\alpha)(1 + \log n) \leq (1-\beta) \log n.$$ This suffices to reach a contradiction.