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.

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.

  • $\begingroup$ In this generality your claim is false. It depends on the problem A. $\endgroup$ – Yuval Filmus Sep 18 '17 at 10:51
  • $\begingroup$ @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. $\endgroup$ – Covvar Sep 18 '17 at 10:55
  • 1
    $\begingroup$ Your new formulation is not the same as the original one. $\endgroup$ – Yuval Filmus Sep 18 '17 at 11:07

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.