2023/02/06 by Mahsa Derakhshan, Derakhshan, Mahsa, Naveen Durvasula +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2302.02567
openalex publication_date 2023/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Our main result is designing an algorithm that returns a vertex cover of G^⋆ with size at most (3/2+ε) times the expected size of the minimum vertex cover, using only O(n/εp) non-adaptive queries. This improves over the best-known 2-approximation algorithm by Behnezhad, Blum, and Derakhshan [SODA'22], who also show that Ω(n/p) queries are necessary to achieve any constant approximation. Our guarantees also extend to instances where edge realizations are not fully independent. We complement this upper bound with a tight 3/2-approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations.