6 papers · 1 filter
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…
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 vertices and edge capacities from in time,…
Maximum Flow by Augmenting Paths in Time
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1
We present a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time, whi…
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 -approximate maximum matching in -node -edge general (not necessarily bipartite) und…
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Aaron Bernstein, Jiale Chen, Aditi Dudeja +3
We consider the foundational problem of maintaining a -approximate maximum weight matching (MWM) in an -node dynamic graph undergoing edge insertions and deleti…
Efficient Matroid Intersection via a Batch-Update Auction Algorithm
Joakim Blikstad, Ta-Wei Tu
Given two matroids and over the same -element ground set, the matroid intersection problem is to find a largest common independent set, whose siz…