Better results for minimum vertex cover algorithms

Currently I'm using the well-known ratio-2 algorithm which is nice and fast, but I'm looking for an intuitive way to improve my results.

All the articles I read so far were way too complicated for me, I'm looking for simple ideas to improve the results.

What I got so far:
def approx_vc(g):
"""
Find a vertex cover that in the worst case is twice the size of the mvc (ratio 2).
:param g: Graph object
:return: Set of integers as vertices.
"""
c = Set()
e = g.get_edges()
while len(e):
u, v = e.pop()
c.update([u, v])
for edge in list(e):
if u in edge or v in edge:
e.remove(edge)
return c


A short trip to wikipedia will tell you that there is no known better approximation algorithm for vertex cover (at least when by "better" we require an improvement by a constant independent of the input).

This is what is known so far:

-
The best known approximation achieves an approximation factor of $2-\Theta\left(\frac{1}{\sqrt{\log V}}\right)$ [1].

-
VC is NP-hard to approximate within a factor of $1.3606$ (meaning that if we have a polynomial approximation algorithm with this factor then $\mathsf{P}=\mathsf{NP})$ [2].

-
If the unique games conjecture holds, then VC is NP-hard to approximate within a factor of $2-\epsilon$, for all $\epsilon>0$ [3]. So if there exists a $2-\epsilon$ approximation for VC, then either $\mathsf{P}=\mathsf{NP}$, or the unique games conjecture fails.

Thus, any better approximations than the naive one you presented will solve open questions in complexity, so you are not likely to find them here (and they might not exist at all).

1. G. Karakostas, A better approximation ratio for the vertex cover problem, ACM Trans. Algorithms (TALG) 5 (4) (2009) 41.

1. Dinur, Irit; Safra, Samuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics. 162 (1): 439–485.

1. Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349.

StackExchange Computer Science Q#66495, answer score: 9