A list heuristic for vertex cover

We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most Δ/2+32 for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than Δ/2.