Basic approximation algorithms understanding

Question

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

• D.W.: 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.
• PlsWork: @D.W. thanks for pointing me in the right direction. I edited the post.
• Yuval Filmus: The answer potentially depends on your definition of "$\alpha$-approximation algorithm". Which definition do you use?
• PlsWork: @YuvalFilmus I edited the question.

Answer 1

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.

• PlsWork: 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.
• Yuval Filmus: No, my example still works.
• Yuval Filmus: 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$.
• PlsWork: You are right, both exact algorithms Alg1 and Alg2 are indeed 2 and 4 approximations.