CARMA SEMINAR Speaker: Prof. Ljiljana Brankovic, School of Electrical Engineering and Computer Science, The University of Newcastle Title: Combining two worlds: Parameterised Approximation for Vertex Cover Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle Time and Date: 4:00 pm, Thu, 29th Nov 2012 Abstract: Parameterised approximation is a relatively new but growing field of interest. It merges two ways of dealing with NP-hard optimisation problems, namely polynomial approximation and exact parameterised (exponential-time) algorithms. We explore opportunities for parameterising constant factor approximation algorithms for vertex cover, and we provide a simple algorithm that works on any approximation ratio of the form $\frac{2l+1}{l+1}$, $l=1,2,\dots$, and has complexity that outperforms previously published algorithms by Bourgeois et al. based on sophisticated exact parameterised algorithms. In particular, for $l=1$ (factor-$1.5$ approximation) our algorithm runs in time $\text{O}^*(\text{simpleonefiveapproxbase}^k)$, where parameter $k \leq \frac{2}{3}\tau$, and $\tau$ is the size of a minimum vertex cover. Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree at most four and a limited number of vertices with degree less than two. [Permanent link]