• 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]