All Questions
2 questions
6
votes
1
answer
274
views
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
It is known 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 for ...
- 9,508
46
votes
4
answers
14k
views
Approximation algorithms for Metric TSP
It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in ...
- 2,257