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$.

$\endgroup$
  • $\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. Sep 19 '17 at 16:06
  • $\begingroup$ @D.W. thanks for pointing me in the right direction. I edited the post. $\endgroup$ – Anna Vopureta Sep 19 '17 at 23:09
  • 1
    $\begingroup$ The answer potentially depends on your definition of "$\alpha$-approximation algorithm". Which definition do you use? $\endgroup$ – Yuval Filmus Sep 20 '17 at 8:52
  • $\begingroup$ @YuvalFilmus I edited the question. $\endgroup$ – Anna Vopureta Sep 20 '17 at 9:56
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.

$\endgroup$
  • $\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$ – Anna Vopureta Sep 20 '17 at 10:16
  • 2
    $\begingroup$ No, my example still works. $\endgroup$ – Yuval Filmus Sep 20 '17 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 Sep 20 '17 at 10:59
  • $\begingroup$ You are right, both exact algorithms Alg1 and Alg2 are indeed 2 and 4 approximations. $\endgroup$ – Anna Vopureta Sep 20 '17 at 11:02

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.