A. Graur

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

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…

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 I^µ^{- 1}$ -time algorithms for computing multiplicative $(1 - I^µ)$ -approximate solutions to multi-commodity flow problems with $k$ -commodities on $m$ -edge dire…

cs.DS2024

Sparse Submodular Function Minimization

Andrei Graur, Haotian Jiang, Aaron Sidford

In this paper we study the problem of minimizing a submodular function $f : 2^{V} \to R$ that is guaranteed to have a $k$ -sparse minimizer. We give a deterministic a…