# Why $\operatorname{gap-A}[1.5a, 1.5b + 1/4]$ has an efficient solution?

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:

1. there's a $y_x\in Y$ such that $y_x > b$.
2. for every $y_x\in Y$: $y_x < a$

If $x$ is not in one of the above the result could be arbitrary.

• In this generality your claim is false. It depends on the problem A. – Yuval Filmus Sep 18 '17 at 10:51
• @YuvalFilmus, I've edited the question and validated it's the original phrasing. This question was taken from some test. I'd be surprised if there were a mistake. – Covvar Sep 18 '17 at 10:55
• Your new formulation is not the same as the original one. – Yuval Filmus Sep 18 '17 at 11:07

## 1 Answer

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) > 1.5a.$$ Conversely, if $opt(x) \leq 1.5a$ then $$val(y_x) \leq 1.5a.$$ You take it from here.

• I see (also I think I understand why the previous formulation of the problem is not identical) - Thanks! – Covvar Sep 18 '17 at 11:10