1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.