Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings

Given a d-dimensional continuous (resp. discrete) probability distribution μ and a discrete distribution nu, the semi-discrete (resp. discrete) Optimal Transport (OT) problem asks for computing a minimum-cost plan to transport mass from μ to nu; we assume n to be the size of the support of the discrete distributions, and we assume we have access to an oracle outputting the mass of μ inside a constant-complexity region in O(1) time. In this paper, we present three approximation algorithms for the OT problem. (i) Semi-discrete additive approximation: For any ε>0, we present an algorithm that computes a semi-discrete transport plan with ε-additive error in nO(d)logfracCmaxε time; here, Cmax is the diameter of the supports of μ and nu. (ii) Semi-discrete relative approximation: For any ε>0, we present an algorithm that computes a (1+ε)-approximate semi-discrete transport plan in nε-O(d)log(n)logO(d)(log n) time; here, we assume the ground distance is any Lp norm. (iii) Discrete relative approximation: For any ε>0, we present a Monte-Carlo (1+ε)-approximation algorithm that computes a transport plan under any Lp norm in nε-O(d)log(n)logO(d)(log n) time; here, we assume that the spread of the supports of μ and nu is polynomially bounded.