Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Stochastic Matching with Few Queries - 1-Epsilon Approximation

Association for Computing Machinery (ACM) via YouTube

Overview

Explore a 24-minute conference talk that delves into the intricacies of stochastic matching with limited queries, presenting a (1-epsilon) approximation algorithm. Learn about the problem definition, examine relevant examples, and understand the contributions made in this field. Gain insights into the proposed algorithm, its analysis outline, and the concept of "Vertex Independent Matchings" for crucial edges. Discover the role of local algorithms and independence in this context, and grasp the key conclusions drawn from this research in computational theory and optimization.

Syllabus

Intro
Problem Definition
Some Examples
Related Work
Our Contribution
The Algorithm
Analysis Outline
"Vertex Independent Matchings" for Crucial Edges
Local Algorithms and Independence
Conclusion

Taught by

Association for Computing Machinery (ACM)

Reviews

Start your review of Stochastic Matching with Few Queries - 1-Epsilon Approximation

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.