2 citations · 3 across the 6 of their papers we have counts for
7 papers
Randomization for Faster Exact Optimization of Discounted Markov Decision Processes
Andrei Graur, Aaron Sidford, Ta-Wei Tu
We provide faster deterministic and randomized algorithms for exactly solving discounted Markov Decision Processes (DMDPs). We obtain our results by efficiently reducing computing…
Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
Li Chen, Andrei Graur, Aaron Sidford
We provide -time algorithms for computing multiplicative -approximate solutions to multi-commodity flow problems with -commodities on -edge direct…
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…
Sparse Submodular Function Minimization
Andrei Graur, Haotian Jiang, Aaron Sidford
In this paper we study the problem of minimizing a submodular function that is guaranteed to have a -sparse minimizer. We give a deterministic a…
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…
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 non-atomic prob…
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 , find an element of $\arg\mi…