I have read that there are approximation algorithms with two different kinds of approximation factors:

  • $c$ . A constant approximation factor.
  • $f(n)$ . An approximation factor that is function of the input size.

However, right know I'm dealing with an approximation factor of the following nature:

  • $f(OPT)$ . Namely, an approximation factor that is a function of the optimal solution size.

Is there an special name for this kind of approximation algorithms?

  • 1
    $\begingroup$ This type of ratio has been described in a number of recent papers, see for example Marx'08 and CCKLMNT'17. The latter, more recent paper refers to this as a Fixed Parameter Approximation Algorithm, or FPT-Approximation. $\endgroup$
    – Yonatan N
    Mar 17 at 1:08
  • 2
    $\begingroup$ This is common for geometric set cover problems. There is no special name for it, because ultimately opt might be $\Theta(n)$, so people are not convinced by the importance of such cases. $\endgroup$ Mar 17 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.