1
$\begingroup$

I read it in not only one place. People write theorems of the form:

Theorem: ALG is an O(1)-approximation algorithm

It means that ALG is a constant factor approximation algorithm but is it safe to say that? I mean it misleads. Why am I asking?

Because, many problems I know of do not have an $\alpha$-approximation algorithm where $\alpha<\gamma$, unless P=NP. For example, the k-center problem does not have an $\alpha$-approximation algorithm where $\alpha<2$, unless P=NP. Well, there is a simple greedy algorithm that is 2-approximation algorithm for the k-center problem. Can we say that this greedy is O(1)-approximation algorithm for the k-center problem? I mean, if it is an O(1)-approximation algorithm for the k-center problem, it is, for example, an 1.9-approximation algorithm, no?

$\endgroup$
6
$\begingroup$

When we say that ALG is an $O(1)$-approximation algorithm, we meant that there exists a constant $C$ such that ALG is a $C$-approximation algorithm. Sometimes we don't care about the exact value of $C$, which is why we use the $O(1)$ notation.

You don't get to choose the constant – rather you are only given that such a constant exists.

$\endgroup$

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.