Stochastic Minimum Vertex Cover with Few Queries: A 3/2-Approximation
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a 30-minute lecture on the stochastic vertex cover problem presented by Mahsa Derakhshan from UC Berkeley at the Simons Institute. Delve into an improved 3/2-approximation algorithm using O(n/p) non-adaptive queries for finding a minimum vertex cover of an unknown random subgraph G* of a known graph G. Learn about the advancement over the previous 2-approximation algorithm and understand why Ω(n/p) queries are necessary for constant approximation. Discover how this result extends to instances with correlated edge realizations and examine the complementary tight 3/2-approximation lower bound for stochastic graphs with mildly correlated edge realizations. Gain insights into sublinear graph simplification techniques and their applications in solving complex graph problems efficiently.
Syllabus
Stochastic Minimum Vertex Cover with Few Queries: a 3/2-approximation
Taught by
Simons Institute
Related Courses
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine LearningAssociation for Computing Machinery (ACM) via YouTube Sublinear Algorithms for Gap Edit Distance
IEEE via YouTube High Dimensional Robust Sparse Regression
Simons Institute via YouTube Learning-Augmented Sketches for Frequency Estimation
Simons Institute via YouTube Adaptive Sparse Recovery with Limited Adaptivity
Simons Institute via YouTube