The Taub Faculty of Computer Science Events and Talks
Monday, 21.06.2021, 16:30
We introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms substantially improve the best known running times of parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set for a wide range of approximation ratios.
The running times of our algorithms are derived from an asymptotic analysis of a broad class of two-variable recurrence relations. Our main theorem gives a simple formula for this asymptotics. The formula can be efficiently calculated by solving a simple numerical optimization problem, and provides the mathematical insight required for the algorithm design. To this end, we show an equivalence between the recurrence and a stochastic process. We analyze this
process using the Method of types, by introducing an adaptation of Sanov's theorem to our setting.
The talk will include a survey of additional results obtained during my PhD studies.