# Basic approximation algorithms understanding

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

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

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

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$.
• 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. – Anna Vopureta Sep 20 '17 at 10:16
• 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$. – Yuval Filmus Sep 20 '17 at 10:59