Ta-Wei Tu

activity

20222026

collaborators

Showing cs.DSShow all

8 papers · 1 filter

cs.DS2026

Near-Optimal Parallel $M$ -Matrix Scaling

Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu

In this paper we consider the problem of computing a positive diagonal scaling of a $d \times d$ symmetric $M$ -matrix so that all row and column sums are $1$ . We provide a poly-log…

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…

cs.DS2024

Matching Composition and Efficient Weight Reduction in Dynamic Matching

Aaron Bernstein, Jiale Chen, Aditi Dudeja +3

We consider the foundational problem of maintaining a $(1 - ε)$ -approximate maximum weight matching (MWM) in an $n$ -node dynamic graph undergoing edge insertions and deleti…

cs.DS2024

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…

cs.DS2023

Entropy Regularization and Faster Decremental Matching in General Graphs

Jiale Chen, Aaron Sidford, Ta-Wei Tu

We provide an algorithm that maintains, against an adaptive adversary, a $(1 - ε)$ -approximate maximum matching in $n$ -node $m$ -edge general (not necessarily bipartite) und…

cs.DS2022

Subquadratic Weighted Matroid Intersection Under Rank Oracles

Ta-Wei Tu

Given two matroids $M_{1} = (V, I_{1})$ and $M_{2} = (V, I_{2})$ over an $n$ -element integer-weighted ground set $V$ , the weighted matroid intersect…

Near-Optimal Parallel M-Matrix Scaling

Randomization for Faster Exact Optimization of Discounted Markov Decision Processes

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

Efficient Matroid Intersection via a Batch-Update Auction Algorithm

Matching Composition and Efficient Weight Reduction in Dynamic Matching

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

Entropy Regularization and Faster Decremental Matching in General Graphs

Subquadratic Weighted Matroid Intersection Under Rank Oracles

Near-Optimal Parallel $M$ -Matrix Scaling

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