2 papers
cs.DS2026
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
cs.DS2025
Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang +1
For -vertex -edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with $\tilde O(m…