Let $0<a < b<1/2$. Suppose that there's an efficient $a/b$-approximation for $A$, where $A$ is a maximization problem. Why does $\operatorname{gap-A}[1.5a, 1.5b +1/4]$ also has a polynomial solution?
We've learned in class that if $gap-A[a,b]$ has a polynomial solution then there's a $\frac{a}{b}$ approximation. That is,
$$\frac{a}{b} opt(x) \le val(y_x) \le opt(x)$$
So let's assume by contradiction that $\operatorname{gap-A}[1.5a, 1.5b +1/4]$ is hard.
Then, there's no polynomial time $\frac{1.5a}{1.5b + 1/4} $-approximation algorithm.
$$\frac{1.5a}{1.5b + 1/4} = \frac{a}{b+1/6}$$
Then, $gap-A[a,b+1/6]$ is hard to decide, but that doesn't help with reaching a contradiction.
EDIT:
We define for a maximization problem $A$ the decision problem $\operatorname{gap-A}[a,b]$ as:
Let $Y$ to be the set of solutions for $x$.
for a given $x$, the algorithm needs to decide:
- there's a $y_x\in Y$ such that $y_x > b$.
- for every $y_x\in Y$: $y_x < a$
If $x$ is not in one of the above the result could be arbitrary.