






















Our main result is designing an algorithm that returns a vertex cover of $\mathcal{G}^\star$ 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。