A. Graur

most citedNew Query Lower Bounds for Submodular Function MInimization

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

collaborators

2 papers

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…