An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Clifford Stein, Miltiadis Stouras, Ola Svensson, Ali Vakilian · 2026
Read An Optimal Algorithm for Stochastic Vertex Cover by Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Clifford Stein, Miltiadis Stouras, Ola Svensson, Ali Vakilian (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-27795.txt.
Description
van den Brand and co-authors settle a core question on stochastic vertex cover. Edges appear at random with known chance p. The algorithm may probe edges one by one. It must guess a near-minimum cover with few probes. Their method reaches a 1 plus epsilon approximation. Probe count scales as order n over p. Past work traded accuracy against a huge extra factor. The new result closes that gap.
Catalog record
| CREATOR | Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Clifford Stein, Miltiadis Stouras, Ola Svensson, Ali Vakilian |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82859 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.27795