Cheap and Secure Web Hosting Provider : See Now

Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm?

, , No Comments
Problem Detail: 

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?

Asked By : 1-approximation

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback