YoVDO

Stochastic Weighted Matching - 1-Epsilon Approximation

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Algorithms Courses Greedy Algorithms Courses Monte Carlo Methods Courses Approximation Algorithms Courses Probabilistic Methods Courses

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

Probability for Computer Science
Indian Institute of Technology Kanpur via Swayam
Exploration with Limited Memory - Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
Association for Computing Machinery (ACM) via YouTube
Probabilistic Methods for Increased Robustness in Machine Learning
Alan Turing Institute via YouTube
X-Ramanujan Graphs
Simons Institute via YouTube
Advances in Applied Probability II
International Centre for Theoretical Sciences via YouTube