# How to use c-gap problems to prove inapproximability?

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.

• When in doubt, always use the definitions. Work from first principles. Aug 11 '19 at 6:41

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.