דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
event speaker icon
אריאל קוליק, הרצאה סמינריונית לדוקטורט
event date icon
יום שני, 21.6.2021, 16:30
event location icon
Zoom Lecture: 99623903736
event speaker icon
מנחה:  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.
[בחזרה לאינדקס האירועים]