4 papers
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, Rasmus Kyng +4
We give the first almost-linear total time algorithm for deciding if a flow of cost at most still exists in a directed graph, with edge costs and capacities, undergoing decreme…
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, - Shortest Path, and Minimum-Cost Flow
Li Chen, Rasmus Kyng, Yang P. Liu +2
We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, - shortest pat…
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Jan van den Brand, Li Chen, Rasmus Kyng +5
We provide an algorithm which, with high probability, maintains a -approximate maximum flow on an undirected graph undergoing -edge additions in amortized $m^{o(1)} ε^{-3…
Exponential Convergence of Sinkhorn Under Regularization Scheduling
Jingbang Chen, Li Chen, Yang P. Liu +2
In 2013, Cuturi [Cut13] introduced the Sinkhorn algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a…