<p>I think for getting 1.99-approximation algorithm this <a href="http://drops.dagstuhl.de/opus/volltexte/2018/9424/" rel="noreferrer">paper</a> by Manurangsi and Trevisan, has the current fastest algorithm. </p>

CC BY-SA 4.0
2019-09-06T22:31:04.620Z
2019-09-06T22:31:04.620Z
A.2
<p>It is <a href="https://cstheory.stackexchange.com/questions/37713/is-the-current-best-approximation-ratio-for-vertex-cover-problem-also-a-lower-bo">known</a> that computing <span class="math-container">$(\sqrt 2 -\epsilon)$</span>-approximation for VC is NP-hard and that UGC implies that even a <span class="math-container">$(2 -\epsilon)$</span>-approximation is hard.</p>

<p>There is also a <a href="https://www.sciencedirect.com/science/article/pii/S0022000017302222?via%3Dihub" rel="nofollow noreferrer">parameterized algorithm</a> for computing a <span class="math-container">$\alpha$</span>-approximation of VC (for <span class="math-container">$\alpha\in[1,2]$</span>).</p>

<p>Considering the standard (non-parameterized) problem and non-polynomial algorithms:</p>

<ul>
<li><strong>What is the fastest known algorithm for computing a <span class="math-container">$1.99$</span>-approximation?</strong></li>
</ul>

<ds.algorithms><graph-algorithms><approximation-algorithms><exp-time-algorithms>
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
R B
# What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

(Asked by: username_0 on 2019-09-06)

It is [known](https://cstheory.stackexchange.com/questions/37713/is-the-current-best-approximation-ratio-for-vertex-cover-problem-also-a-lower-bo) that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.

There is also a [parameterized algorithm](https://www.sciencedirect.com/science/article/pii/S0022000017302222?via%3Dihub) for computing a $\alpha$-approximation of VC (for $\alpha\in[1,2]$).

Considering the standard (non-parameterized) problem and non-polynomial algorithms:

* **What is the fastest known algorithm for computing a $1.99$-approximation?**

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, exp-time-algorithms


---

## 1 answers

### Answer by username_1 on 2019-09-06. Score: 8 | Accepted answer

I think for getting 1.99-approximation algorithm this [paper](http://drops.dagstuhl.de/opus/volltexte/2018/9424/) by Manurangsi and Trevisan, has the current fastest algorithm.


---

