<p>I have read that there are approximation algorithms with two different kinds of approximation factors:</p>
<ul>
<li><span class="math-container">$c$</span> . A constant approximation factor.</li>
<li><span class="math-container">$f(n)$</span> . An approximation factor that is function of the input size.</li>
</ul>
<p>However, right know I'm dealing with an approximation factor of the following nature:</p>
<ul>
<li><span class="math-container">$f(OPT)$</span> . Namely, an approximation factor that is a function of the optimal solution size.</li>
</ul>
<p>Is there an special name for this kind of approximation algorithms?</p>

CC BY-SA 4.0
2021-03-17T01:08:06.560Z
This type of ratio has been described in a number of recent papers, see for example [Marx'08](https://people.csail.mit.edu/rrw/presentations/marx-approx.pdf) and [CCKLMNT'17](https://arxiv.org/pdf/1708.04218.pdf). The latter, more recent paper refers to this as a Fixed Parameter Approximation Algorithm, or FPT-Approximation.
Yonatan N
CC BY-SA 4.0
2021-03-17T01:51:56.197Z
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.
Sariel Har-Peled
<approximation-algorithms>
Is there a name for approximation algorithms with $f(OPT)$ approximation factor?
jesús garcía
# Is there a name for approximation algorithms with $f(OPT)$ approximation factor?

(Asked by: username_0 on 2021-03-16)

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?

**Tags:** approximation-algorithms
> **Comments:**
> **username_1**: This type of ratio has been described in a number of recent papers, see for example [Marx'08](https://people.csail.mit.edu/rrw/presentations/marx-approx.pdf) and [CCKLMNT'17](https://arxiv.org/pdf/1708.04218.pdf). The latter, more recent paper refers to this as a Fixed Parameter Approximation Algorithm, or FPT-Approximation.  
> **username_2**: 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.  

---

## 0 answers

