Ta-Wei Tu

collaborators

3 papers

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

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

Aaron Bernstein, Joakim Blikstad, Jason Li +2

We give a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from ${1, \dots, U}$ in $O ~ (n^{2} lo g U)$ time,…

cs.DS2025

Maximum Flow by Augmenting Paths in $n^{2 + o (1)}$ Time

Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from ${1, \dots, U}$ in $n^{2 + o (1)} lo g U$ time, whi…

Randomization for Faster Exact Optimization of Discounted Markov Decision Processes

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

Maximum Flow by Augmenting Paths in n2+o(1) Time

Maximum Flow by Augmenting Paths in $n^{2 + o (1)}$ Time