Andrei Graur

activity

20222025

most citedParallel Submodular Function Minimization

1 citations · 1 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2025

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs

Li Chen, Andrei Graur, Aaron Sidford

We provide $m^{1 + o (1)} k ε^{- 1}$ -time algorithms for computing multiplicative $(1 - ε)$ -approximate solutions to multi-commodity flow problems with $k$ -commodities on $m$ -edge direct…

cs.DS2023★ 1 cited

Parallel Submodular Function Minimization

Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang +1

We consider the parallel complexity of submodular function minimization (SFM). We provide a pair of methods which obtain two new query versus depth trade-offs a submodular function…

cs.DS2022

Improved Lower Bounds for Submodular Function Minimization

Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang +1

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prov…