AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and 3-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random 1.5-approximation algorithm for Vertex Cover, whose running time of O*(1.01657k) substantially improves the best known running time of O*(1.0883k) [Brankovic and Fernau, 2013]. For 3-Hitting Set we present a parameterized random 2-approximation algorithm with running time of O*(1.0659k), improving the best known O*(1.29k) algorithm of [Brankovic and Fernau, 2012]. The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations. We show an equivalence between these recurrences and a stochastic process, which we analyze using the Method of Types, by introducing an adaptation of Sanov's theorem to our setting.

Roohani Sharma

+49 681 9325 1116

Zoom

527 278 8807

passcode not visible

logged in users only

The talk will be in hybrid format. The in-person participants meet in room 024 at MPII and the hybrid participants can join via the zoom link given above. If you wish to attend online and do not have the password for the zoom link, please contact Roohani Sharma at rsharma@mpi-inf.mpg.de.