Stochastic Minimum Vertex Cover with Few Queries: A 3/2-Approximation

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.