2
$\begingroup$

I was reading on wikipedia about the approximations of the Vertex Cover problem and saw that an approximation algorithm with an approximation factor of $\displaystyle 2 - \Theta \left( \frac{1}{\sqrt{\log |V|}} \right)$ is known.

I want to understand how to read that expression.

Any help small or big would be appreciated.

$\endgroup$
0
$\begingroup$

lets say $f(|V|)$ is the real approximation factor. then $f(|V|) = 2-\Theta \left( \frac{1}{\sqrt{\log |V|}} \right ) $ means the same as $2-f(|V|) = \Theta \left ( \frac{1}{\sqrt{\log |V|}} \right ) $ which means that $\frac{k_2}{\sqrt{\log |V|}} \leq 2-f(|V|) \leq \frac{k_1}{\sqrt{\log |V|}} $ for some constant $k_1,k_2$

(source: https://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations)

$\endgroup$
0
$\begingroup$

Without reading the article myself:

I assume this means that in the limit, the approximation factor is 2, and it approaches $2$ with a function that is in $$\Theta\left(\frac{1}{\sqrt{log|V|}}\right)$$

Or in other words, the smaller the graph, the better the approximation, but never worse than $2$ (i assume).

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