A. Graur

activity

20192025

most citedNew Query Lower Bounds for Submodular Function MInimization

2 citations · 2 across the 2 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

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.DS2020

Efficient Splitting of Measures and Necklaces

Noga Alon, Andrei Graur

We provide approximation algorithms for two problems, known as NECKLACE SPLITTING and $ε$ -CONSENSUS SPLITTING. In the problem $ε$ -CONSENSUS SPLITTING, there are $n$ non-atomic prob…

cs.DS2019★ 2 cited

New Query Lower Bounds for Submodular Function MInimization

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy +1

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function $f : 2^{[n]} \to R$ , find an element of $\arg\mi…