Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Offered By: IEEE via YouTube
Course Description
Overview
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.
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
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube