Approximating optimal transport with linear programs
classification
💻 cs.DS
keywords
optimaltransportadditiveapproximationslinearprogramsalgorithmsapproximating
read the original abstract
In the regime of bounded transportation costs, additive approximations for the optimal transport problem are reduced (rather simply) to relative approximations for positive linear programs, resulting in faster additive approximation algorithms for optimal transport.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
A grid-sketching technique enables ε-accurate estimation of W₂² between α-Hölder smooth distributions on (0,1)^d in time ε^{-max(2, (d+1+o(1))/(1+α))}.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.