Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
event speaker icon
Ariel Kulik (Ph.D. Thesis Seminar)
event date icon
Monday, 21.06.2021, 16:30
event location icon
Zoom Lecture: 99623903736
event speaker icon
Advisor: Prof. H. Shachnai
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.