2
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I see (also I think I understand why the previous formulation of the problem is not identical) - Thanks! $\endgroup$
    – Covvar
    Sep 18, 2017 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.