Why $\operatorname{gap-A}[1.5a, 1.5b + 1/4]$ has an efficient solution? Let $0&lt;a &lt; b&lt;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 &gt; b$.
for every $y_x\in Y$: $y_x &lt; a$


If $x$ is not in one of the above the result could be arbitrary.
Given an instance $x$ of $\mathsf{gap\text{-}A}(1.5a,1.5b+1/4)$, calculate $y_x$ using the $a/b$ approximation algorithm, so that
$$
\frac{a}{b} opt(x) \leq val(y_x) \leq opt(x).
$$
If $opt(x) \geq 1.5b+1/4$ then
$$
val(y_x) \geq \frac{a}{b} (1.5b+1/4) &gt; 1.5a.
$$
Conversely, if $opt(x) \leq 1.5a$ then
$$
val(y_x) \leq 1.5a.
$$
You take it from here.