93 citations · 537 across the 73 of their papers we have counts for
4 papers · 1 filter
Fast Algorithms for -Regression
Deeksha Adil, Rasmus Kyng, Richard Peng +1
The -norm regression problem is a classic problem in optimization with wide ranging applications in machine learning and theoretical computer science. The goal is to comput…
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…
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
Sally Dong, Yu Gao, Gramoz Goranci +4
We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm fo…
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Li Chen, Rasmus Kyng, Yang P. Liu +3
We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral demands, costs, and capacities in…