Seminar • Algorithms and Complexity • Stochastic Minimum Vertex Cover with Few Queries: A 3/2-approximation
Please note: This seminar will take place in DC 3317 and online.
Mahsa Derakhshan, Assistant Professor
Khoury College of Computer Sciences, Northeastern University
In this talk, we discuss the stochastic vertex cover problem. In this problem, G is an arbitrary known graph, and G* is an unknown random subgraph of G containing each of its edges independently with a known probability p. Edges of G* can only be verified using edge queries. The goal in this problem is to find a minimum vertex cover of G* using a small number of queries.