Stochastic minimum vertex cover in general graphs: a \(3/2\)-approximation

DOI10.1145/3564246.3585230MaRDI QIDQ6499227

Mahsa Derakhshan, Nika Haghtalab, Naveen Durvasula

Publication date: 8 May 2024

zbMATH Keywords

stochastic optimizationminimum vertex cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stochastic matching on uniformly sparse graphs
• Price of Correlations in Stochastic Optimization
• Covering minimum spanning trees of random subgraphs
• Shortest‐path metric approximation for random subgraphs
• Fully Dynamic Matching in Bipartite Graphs
• On Estimating Maximum Matching Size in Graph Streams
• Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries
• Stochastic matching with few queries: (1-ε) approximation
• Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Probabilistic Set Covering with Correlations
• Tight bounds for single-pass streaming complexity of the set cover problem
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

This page was built for publication: Stochastic minimum vertex cover in general graphs: a \(3/2\)-approximation