2
$\begingroup$

We say that "An algorithm is a $\beta$-approximation to problem $X$, if for any instance of problem $X$, the solution returned by this algorithm is within a factor $\beta$ of the optimal solution".

Now assume that we have a $\log(N)$-approximation algorithm (called it Alg 1) for problem $X$ where $N$ is the size of problem $X$. Further assume there is one other algorithm (called it Alg 2) for problem $X$, but for that algorithm we could find an instance of problem $X$ with size $N$ such that the solution returned by Alg 2 is $N/2$ times of the optimal solution.

What is a correct way of saying this statement that clearly shows that Alg 1 is much more better than Alg 2? I was thinking about the following one:

"Alg 2 provides a $\beta$-approximation to problem $X$ where $\beta \geq N/2$."

Is this correct? Any better suggestion?

$\endgroup$
2
$\begingroup$

I would write something like this: whereas Alg 1 is a $\log(N)$-approximation algorithms, there are instances on which the approximation ratio of Alg 2 is only $N/2$. So Alg 1 is much better (in the worst case) than Alg 2.

$\endgroup$
  • $\begingroup$ One question: saying Alg 1 is "much better" is okay for a paper? Or you think these relative terms are not exact? $\endgroup$ – m0_as Oct 11 '17 at 21:12
  • 2
    $\begingroup$ Not everything you write in a paper has to be exact – only the mathematical parts. "Much better" is as good a phrase as any. $\endgroup$ – Yuval Filmus Oct 11 '17 at 21:38

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.