0
$\begingroup$

I am trying to learn about approximation algorithms. In some research papers, it is mentioned about the absolute approximation ratio. what does the absolute approximation ratio mean? is it different from the asymptotic approximation ratio?

if there is any resource that might help to understand more about this, please leave it here. Thank you

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I encourage you to edit your post to provide context, and in particular, to identify the paper(s) you've been reading that refer to absolute approximation ratio. It would help to list one or two examples, provide a full reference (title, authors, where published, and if possible, a link to a PDF that is freely available) as well as where in the paper refers to this concept. Does the paper define this term? Have you looked through the papers it cites to see if it defines that term? $\endgroup$
    – D.W. ♦
    Dec 20, 2022 at 6:11
  • $\begingroup$ You might check from context whether it is the same as the "absolute performance guarantee" from en.wikipedia.org/wiki/Approximation_algorithm $\endgroup$
    – D.W. ♦
    Dec 20, 2022 at 6:13
  • $\begingroup$ My guess is that this is the difference between $\alpha \cdot \mathit{OPT}$ and $\alpha \cdot \mathit{OPT} + \beta$. $\endgroup$
    – Yuval Filmus
    Dec 20, 2022 at 22:06

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.