We explore opportunities for parameterising constant factor approximation algorithms for vertex cover. We provide a simple algorithm that works on any approximation ratio of the form 2ι+1/ι+1 and has complexity that outperforms an algorithm by Bourgeois et al. derived from a sophisticated exact parameterised algorithm. In particular, for ι = 1 (factor 1.5 approximation) our algorithm runs in time O*(1.09k). Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree four.
Relation
21st International Symposium on Algorithms and Computation (ISAAC 2010). Algorithms and Computation: Proceedings of the 21st International Symposium (ISAAC 2010), Part 1 (Jeju Island, Korea 15-17 December, 2010) p. 390-402