Overcoming Computational Complexity Barriers for Optimal Transport in Discrete and Semi-Discrete Settings

Given two probability distributions $mu$ and $nu$, Optimal Transport (OT) measures the minimum effort required to transport mass between $mu$ and $nu$. OT provides a meaningful distance between distributions and acts as a dissimilarity measure between them. Due to its useful statistical properties, OT cost has been used in numerous machine-learning applications. More formally, given a $d$-dimensional continuous (resp. discrete) probability distribution $mu$ defined over a support Asubsetmathbb{R}^d and a discrete distribution $nu$ defined over a support Bsubsetmathbb{R}^d, the semi-discrete (resp. discrete) optimal transport problem asks for computing a minimum-cost plan to transport mass between $mu$ and $nu$. In the special case of the discrete OT problem, where $mu$ and $nu$ are defined on sets $A$ and $B$ of $n$ points each, and any point in $Acup B$ is given $1/n$ mass, the problem is equivalent to the minimum-cost bipartite matching problem. In this thesis, we study the semi-discrete OT and the minimum-cost bipartite matching problems. The sensitivity of OT to noise has motivated the study of robust variants. Two such formulations are: (i) the $alpha$-optimal partial transport, which is the minimum cost required to transport a mass of $alpha$, and (ii) the $lambda$-robust optimal transport, which regularizes the OT problem using the total variation (TV) distance. For a continuous distribution $mu$ defined over a bounded support Asubset mathbb{R}^d and a discrete distribution $nu$ with a support Bsubset mathbb{R}^d of $n$ points, suppose C_max denotes the diameter of the supports of $mu$ and $nu$ and assume we have access to an oracle that outputs the mass of $mu$ inside a constant-complexity region in $O(1)$ time. In this thesis, given a parameter $varepsilon>0$, we present the following results for the semi-discrete OT problem between $mu$ and $nu$: 1. Additive approximation for semi-discrete OT: We present an $varepsilon$-additive approximation algorithm for the semi-discrete OT problem that runs in n^O(d)logfrac{C_max}{varepsilon} time. Our algorithm works for several ground distances, including the ell_p-norm and the squared-Euclidean distance. 2. Combinatorial algorithm for semi-discrete OT: We propose a combinatorial framework for the semi-discrete OT, which can be viewed as an extension of the combinatorial framework for the discrete OT but requires several new ideas. We present a new algorithm that for $2$-dimensional settings, computes an $varepsilon$-additive approximate semi-discrete transport plan in tilde{O}(n⁴log frac{1}{varepsilon}) time. 3. Combinatorial algorithm for semi-discrete robust OT: We provide a novel characterization of the optimal solutions to the semi-discrete robust OT problem and show that they can be represented as a restricted Voronoi diagram. We also present an algorithm that computes an $varepsilon$-additive approximate solution in O(n⁴log nlog frac{1}{varepsilon}) time in $2$ dimensions and n^d+2log (1/ varepsilon) time in $d$ dimensions. Furthermore, for point sets $A$ and $B$ of size $n$, let $Delta$ be the spread, i.e., the ratio of the distance of the farthest to the closest pair of points in $Acup B$. Furthermore, let $Phi(n)$ be the query/update time of a $d$-dimensional dynamic weighted bichromatic closest pair data structure. For point sets in $d$ dimensions, in this thesis, we present the following result for the bipartite matching problem: 4. Robust algorithm for stochastic Euclidean matching: We present a new algorithm to compute a minimum-cost bipartite matching under Euclidean distances between $A$ and $B$ with a worst-case execution time of tilde{O}(n²Phi(n) log Delta). However, when $A$ and $B$ are drawn independently and identically from a fixed distribution that is not known to the algorithm, the execution time of our algorithm is, in expectation, tilde{O}(n^{2-frac{1}{2d}}Phi(n)log Delta). For any given metric space, obtaining an optimal solution to the offline version of the classical $k$-server problem reduces to solving a minimum-cost partial bipartite matching between two point sets $A$ and $B$ within that metric space. Our final result in this thesis is the following: 5. Efficient exact offline algorithm for $k$-server: We present an {tilde{O}(n^{2-frac{1}{2d+1}}Phi(n)log Delta)} time algorithm for solving the instances of minimum-cost partial bipartite matching defined by the offline version of the $k$-server problem.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Computer Science & Applications

Department dc:contributor.department

Computer Science and#38; Applications

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2025

Author dc:creator

• Shirzadian, Pouyan

Chair dc:contributor.committeechair

• Raghvendra, Sharath

Committee members dc:contributor.committeemember

• Sikora, Jamie
• Ji, Bo
• Agarwal, Pankaj
• Heath, Lenwood S.

• Optimal Transport
• Exact Algorithms
• Wasserstein Distance

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:44668

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/137888