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.

Stochastic Minimum Vertex Cover with Few Queries: a 3/2-approximation