New answers tagged approximation-algorithms
4
The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the Set Cover problem which is NP-hard to approximate within a factor of $(1-\alpha)\cdot N$ where $N$ is the input size [1].
First, we use the standard reduction from Set Cover to ...
Top 50 recent answers are included
