Stochastic Weighted Matching - 1-Epsilon Approximation
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 29-minute IEEE conference talk on stochastic weighted matching, presented by Soheil Behnezhad and Mahsa Derakhshan from UMD. Delve into the (1-epsilon) approximation algorithm, starting with an introduction to the problem definition and its pictorial representation. Examine various algorithms, including Monte Carlo analysis and the greedy approach. Investigate key concepts such as the Weighted "Vertex-Independent Matching Lemma" and the challenges posed by low-probability high-weight edges. Gain insights into the lack of a "Sparsification Lemma" and conclude with a high-level overview of the final analysis, providing a comprehensive understanding of this complex topic in algorithmic graph theory.
Syllabus
Intro
Problem Definition
The Problem, Pictorially
Let's See Some Algorithms.
Analysis of Monte Carlo
The Weighted "Vertex-Independent Matching Lemma"
Low-Probability High-Weight Edges (cont'd)
Lack of "Sparsification Lemma"
The Greedy Algorithm
High-Level Overview of the Final Analysis
Conclusion
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