Explore the analysis of two-variable recurrence relations and their application to parameterized approximations in this 19-minute IEEE conference talk. Delve into topics such as Vertex Cover (VC), parameterized approximation algorithms, and success probability calculations. Learn about generalizing recurrences and understand the main theorem through examples. Gain insights from authors Ariel Kulik and Hadas Shachnai from Technion as they present their research on this complex subject in computer science and algorithmic analysis.
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Overview
Syllabus
Intro
Talk Overview
Vertex Cover (VC)
Vertex Cover (Cont'd)
Parameterized Approximation
A Parameterized Algorithm
Success Probability (cont'd)
Related Work - Recurrences
Generalizing the Reccurence
Recurrence Relations
Main Theorem - Example
Taught by
IEEE FOCS: Foundations of Computer Science
