On the hardness of approximating minimum vertex cover

By Irit Dinur, Shmuel Safra. 2005

730 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/247f9fc1d062872de8ab827d1e229b56d74c9be0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Oded Regev
2. Subhash Khot
3. Nina Mazyavkina
4. Sergey Ivanov
5. S. Sviridov
6. Evgeny Burnaev
7. Chris Peikert
8. Daniele Micciancio

In Computer Graphics and Computer-Aided Design

1. Subhash Khot
2. Nina Mazyavkina
3. Oded Regev
4. Sergey Ivanov
5. S. Sviridov
6. Evgeny Burnaev

Citations in the corpus

• Vertex cover might be hard to approximate to within 2-/spl epsiv/ (2003, methodology): “It follows by combining the Russo-Margulis Theorem and Friedgut’s Theorem, as was done in [10].”
• Reinforcement Learning for Combinatorial Optimization: A Survey (2020, methodology): “such that no two vertices in Sare connected by an edge of E, and ðSðis minimized. MVC problem has a factor-2 approximation [27], and there is a known inapproximability result below the factor of 1.36 [28]. For exact solutions solvers such as Gurobi or CPLEX are used. TSP can be solved exactly with c”