1
$\begingroup$

Question:

Suppose we have 2 algorithms $Alg1$ and $Alg2$ for the same minimization problem. We know that $Alg1$ is a $2$-approximation algorithm and $Alg2$ a $4$-approximation algorithm.

Is the following statement true?

There must be an input $I$ such that $Alg2(I) \geq 2 \cdot Alg1(I)$.

My answer:

I think the statement is false:

In order to prove that the statement is false it is sufficient to find one case where $Alg1$ is a $2$-approximation and $Alg2$ is a 4 approximation and that there is no input which satisfies the inequality from the statement.

Does my approach make sense? Is there some other approach or thought process which proves statements of this type true/false that I'm missing?

Note:

$Alg$ is a $\rho$-approximation algorithm for a minimization problem $\iff$ $\forall I.(OPT(I) \leq Alg(I) \leq \rho \cdot OPT(I))$ where $\rho > 1$ and $OPT(I)$ denotes the optimal solution to the minimization problem for the input $I$.

Improve this question
$\endgroup$
4
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Sep 19, 2017 at 16:06
  • $\begingroup$ @D.W. thanks for pointing me in the right direction. I edited the post. $\endgroup$
    – PlsWork
    Commented Sep 19, 2017 at 23:09
  • 1
    $\begingroup$ The answer potentially depends on your definition of "$\alpha$-approximation algorithm". Which definition do you use? $\endgroup$
    – Yuval Filmus
    Commented Sep 20, 2017 at 8:52
  • $\begingroup$ @YuvalFilmus I edited the question. $\endgroup$
    – PlsWork
    Commented Sep 20, 2017 at 9:56

1 Answer 1

Reset to default
1
$\begingroup$

According to your definition (which is the standard definition), an algorithm solving a certain minimization problem is an $\alpha$-approximation algorithm for any $\alpha \geq 1$.

Consider a minimization problem solvable in polynomial time, for example minimum cut. Let Alg1 and Alg2 be algorithms solving this problem exactly. Alg1 is a 2-approximation algorithm and Alg2 is a 4-approximation algorithm, yet there is no input on which Alg2 performs worse than Alg1.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I wouldn't call $\alpha \geq 1$ the standard definition, rather $\alpha > 1$. Anyways, I use $\alpha > 1$ in which case your example doesn't work. I edited the post to include this info. $\endgroup$
    – PlsWork
    Commented Sep 20, 2017 at 10:16
  • 2
    $\begingroup$ No, my example still works. $\endgroup$
    – Yuval Filmus
    Commented Sep 20, 2017 at 10:40
  • $\begingroup$ If you apply the definition that you yourself wrote, you will see that Alg1 and Alg2 are indeed $c$-approximation algorithms for any $c > 1$. $\endgroup$
    – Yuval Filmus
    Commented Sep 20, 2017 at 10:59
  • $\begingroup$ You are right, both exact algorithms Alg1 and Alg2 are indeed 2 and 4 approximations. $\endgroup$
    – PlsWork
    Commented Sep 20, 2017 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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