How to use c-gap problems to prove inapproximability?

Question

Suppose there is a specific set function with some properties - $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized. My goal is to show that designing a constant factor approximation algorithm in polynomial time is NP-Hard.

Correct me if I am wrong: As per these notes on gap reductions, we can design a c-gap problem with $OPT$ being the maximum value of $f$. The problem takes as input $\beta$. The goal is to answer YES if $OPT\geq \beta$. NO if $OPT< c\cdot \beta$. (here $c<1$).

To show the desired inapproximability, it would suffice to show the above c-gap problem is NP-Hard. My question is: Why is it this decision problem is designed for one $\beta$ when the optimimum value for the maximization problem is not known? Is the idea that, suppose you have a solver for the c-gap problem, you can call it with multiple values of $\beta$? If so, how many calls are possible?

Also any additional references on proving inapproximability would be greatly appreciated.

Answer 1

One way to show that there is no polynomial time approximation algorithm with ratio $c$ for a certain problem X (assuming P≠NP) is to give a reduction $f$ from an NP-hard problem Y to X such that:

• If $x$ is a Yes instance then the optimal value for X is at least $\beta(x)$, where $\beta(x)$ can be computed from $x$ in polynomial time.
• If $x$ is a No instance then the optimal value for $X$ is less than $c\beta(x)$ (for the same $\beta(x)$).

Any approximation algorithm for X whose approximation ratio is $c$ can be used to solve Y via the reduction $f$. Therefore, there cannot be any such efficient approximation algorithm unless P=NP.

I'll let you figure out the proof of these two statements.