290 citations · 492 across the 36 of their papers we have counts for
5 papers · 1 filter
Hardness results for Multimarginal Optimal Transport problems
Jason M. Altschuler, Enric Boix-Adsera
Multimarginal Optimal Transport (MOT) is the problem of linear programming over joint probability distributions with fixed marginals. A key issue in many applications is the comple…
Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure
Jason M. Altschuler, Enric Boix-Adsera
Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the s…
Wasserstein barycenters can be computed in polynomial time in fixed dimension
Jason M. Altschuler, Enric Boix-Adsera
Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whe…
Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
Jason M. Altschuler, Pablo A. Parrilo
We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous wor…
Near-linear convergence of the Random Osborne algorithm for Matrix Balancing
Jason M. Altschuler, Pablo A. Parrilo
We revisit Matrix Balancing, a pre-conditioning task used ubiquitously for computing eigenvalues and matrix exponentials. Since 1960, Osborne's algorithm has been the practitioners…