Ta-Wei Tu

activity

20242026

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

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

Efficient Matroid Intersection via a Batch-Update Auction Algorithm

Joakim Blikstad, Ta-Wei Tu

Given two matroids $M_{1}$ and $M_{2}$ over the same $n$ -element ground set, the matroid intersection problem is to find a largest common independent set, whose siz…