# Approximate Earth Mover’s Distance in Truly-Subquadratic Time

Lorenzo Beretta  BARC, University of Copenhagen<EMAIL_ADDRESS>Aviad Rubinstein  Stanford University<EMAIL_ADDRESS>
###### Abstract

We design an additive approximation scheme for estimating the cost of the min-
weight bipartite matching problem: given a bipartite graph with non-negative
edge costs and $\varepsilon>0$, our algorithm estimates the cost of matching
all but $O(\varepsilon)$-fraction of the vertices in truly subquadratic time
$O(n^{2-\delta(\varepsilon)})$.

  * •

Our algorithm has a natural interpretation for computing the Earth Mover’s
Distance (EMD), up to a $\varepsilon$-additive approximation. Notably, we make
no assumptions about the underlying metric (more generally, the costs do not
have to satisfy triangle inequality). Note that compared to the size of the
instance (an arbitrary $n\times n$ cost matrix), our algorithm runs in
sublinear time.

  * •

Our algorithm can approximate a slightly more general problem: max-cardinality
bipartite matching with a knapsack constraint, where the goal is to maximize
the number of vertices that can be matched up to a total cost $B$.

##  1 Introduction

Earth Mover’s Distance (EMD - sometimes also Optimal Transport,
Wasserstein-$1$ Distance or Kantorovich–Rubinstein Distance) is perhaps the
most important and natural measure of similarity between probability
distributions over elements of a metric space [Vil+09, San15, PC19]. Formally,
given two probability distributions $\mu$ and $\nu$ over a metric space
$(\mathcal{M},d)$ their EMD is defined as

$\displaystyle\mathrm{EMD}(\mu,\nu)=\min\left\\{\textnormal{E}_{(x,y)\sim\zeta}[d(x,y)]\;\Big{|}\;\zeta\text{
is a couplingof $\mu$ and $\nu$}\right\\}.$ (1)

When $\mu$ and $\nu$ are discrete distributions with support size $n$ (perhaps
after a discretization preprocessing), a straightforward algorithm for
estimating their EMD is to sample $\Theta(n)$ elements from each, compute all
$\Theta(n^{2})$ pairwise distances, and then compute a bipartite min-weight
perfect matching. This algorithm clearly takes at least $\Omega(n^{2})$ time
(even ignoring the computation of the matching), and incurs a small additive
error due to the sampling.

Our main result is an asymptotically faster algorithm for estimating the EMD:

######  Theorem 1 (Main Theorem).

Suppose we have sample access to two distributions $\mu,\nu$ over metric space
$(\mathcal{M},d)$ satisfying $d(\cdot,\cdot)\in[0,1]$ and query access to $d$.
Suppose further that $\mu,\nu$ have support size at most $n$.

For each constant $\gamma>0$ there exists a constant $\varepsilon>0$ and an
algorithm running in time $O(n^{2-\varepsilon})$ that outputs
$\widehat{\mathrm{EMD}}$ such that

$\widehat{\mathrm{EMD}}\in[\mathrm{EMD}(\mu,\nu)\pm\gamma].$

Moreover, such algorithm takes $\tilde{O}(n)$ samples from $\mu$ and $\nu$.

Notably, our algorithm makes no assumption about the structure of the
underlying metric. In fact, it can be an arbitrary non-negative cost function,
i.e. we do not even assume triangle inequality.

#### Beyond bounded support size.

Support size is a brittle matter; indeed two distributions that are
arbitrarily close in total variation (TV) distance (or EMD) can have
completely different support size. Moreover, for continuous distributions, the
notion of support size is clearly inappropriate and yet we would like to
compute their EMD through sampling. To obviate this issue, Corollary 1.1
generalize Theorem 1 to distributions that are _close_ in EMD to some
distributions with support size $n$.

######  Corollary 1.1.

Suppose we have sample access to two distributions $\mu,\nu$ over metric space
$(\mathcal{M},d_{\mathcal{M}})$ satisfying $d(\cdot,\cdot)\in[0,1]$ and query
access to $d$. Suppose further that there exist $\mu^{\prime},\nu^{\prime}$
with support size $n$ such that
$\mathrm{EMD}(\mu,\mu^{\prime}),\mathrm{EMD}(\nu,\nu^{\prime})\leq\xi$, for
some $\xi>0$.

For each constant $\gamma>0$ there exists a constant $\varepsilon>0$ and an
algorithm running in time $O(n^{2-\varepsilon})$ that outputs
$\widehat{\mathrm{EMD}}$ such that

$\widehat{\mathrm{EMD}}\in[\mathrm{EMD}(\mu,\nu)\pm(4\xi+\gamma)].$

Moreover, such algorithm takes $\tilde{O}(n)$ samples from $\mu$ and $\nu$.

For continuous $\mu$, requiring that $\mu$ is close in EMD to a distribution
with bounded support size is equivalent to saying that $\mu$ can be
discretized effectively for $\mathrm{EMD}$ computation. Thus, such assumption
is natural while computing $\mathrm{EMD}$ between continuous distribution
through discretization.

We stress that the algorithm in Corollary 1.1 does not assume knowledge of
$\mu^{\prime}$ (nor $\nu^{\prime}$) beyond its support size $n$. Indeed, the
empirical distribution over $\tilde{O}(n)$ samples from $\mu$ (resp. $\nu$)
makes a good approximation in $\mathrm{EMD}$. Finally, the sample complexity
in Theorem 1 and Corollary 1.1 is optimal, up to $\mathrm{polylog}(n)$
factors. Indeed, Theorem 1 in [VV10] implies a lower bound of
$\tilde{\Omega}(n)$ on the sample complexity of testing EMD closeness222While
deriving the lower bound from [VV10] takes some work, Remark 5.13 in [Can20]
explicitly states a $\Omega(n/\log n)$ lower bound for TV closeness testing..

#### Matching with knapsack constraint.

Applying our main algorithm to a graph-theory setting, we give an
approximation scheme for a knapsack bipartite matching problem, where our goal
is to estimate the number of vertices that can be matched subject to a total
budget constraint.

######  Theorem 2 (Main theorem, graph interpretation).

For each constant $\gamma>0$, there exists a constant $\varepsilon>0$, and an
algorithm running in time $O(n^{2-\varepsilon})$ with the following
guarantees. The algorithm takes as input a budget $B$, and query access to the
edge-cost matrix of an undirected, bipartite graph $G$ over $n$ vertices. The
algorithm returns an estimate $\widehat{M}$ that is within $\pm\gamma n$ of
the size of the maximum matching in $G$ with total cost at most $B$.

###  1.1 Relaed Work

Computing EMD is an important problem in machine learning [PC19] with some
exemplary applications in computer vision [RTG00, ACB17, Sol+15] and natural
language processing [Kus+15, Yur+19]. See [PC19] for a comprehensive overview.

#### Exact solution.

Computing EMD between two sets of $n$ point boils down to computing the
minimum cost of a perfect matching on a bipartite graph, a problem with a
$70$-years history [Kuh55]. Min-weight bipartite perfect matching can be cast
as a min-cost flow (MCF) instance and to date we can solve it in $n^{2+o(1)}$
time (namely, near-linear in the size of the distance matrix) [Che+22].
Apparently, any exact algorithm requires inspecting the entire distance
matrix, thus $\Theta(n^{2})$ time is the best we can hope for. In addition,
even in $d$-dimensional Euclidean space, where the input has size $d\cdot n\ll
n^{2}$, no $O(n^{2-\varepsilon})$ algorithm exists333The lower bound in
[Roh19] holds in dimension $d=2^{\Omega(\log^{*}n)}$., unless SETH is false
[Roh19].

#### Multiplicative approximation.

A significant body of work has investigated multiplicative approximation of
EMD [Cha02, Ind03, Che+22a, Aga+22, AS14, AZ23, AIK08, And+09, And+14], where
the most commonly studied setting is the Euclidean space (or, more generally,
$\ell_{p}$). If the dimension is constant we have near-linear time
approximation schemes [SA12, And+14, Aga+22, FL22], whereas the high-
dimensional case is more challenging. Only recently [AZ23] broke the
$O(n^{2})$ barrier for $(1+\varepsilon)$-approximation of EMD, building on
[HIS13].

The landscape is much less interesting for general metrics. Indeed, a
straightforward counterexample from [Băd+05] shows that any
$O(1)$-approximation requires $\Omega(n^{2})$ queries to the distance matrix.
This suggests that for general metrics we should content ourselves with a
additive approximation.

#### Additive approximation.

Additive approximation for EMD has been extensively studied by optimization
and machine learning communities [ANR17, Bla+18, DGK18, LXH23, Cut13, Le+21,
Pha+20].

An extremely popular algorithm to solve optimal transport in practice is
Sinkhorn algorithm [Cut13] (see [Le+21, Pha+20] for recent work). Sinkhorn
distance SNK is defined by adding an entropy regularization term $-\eta\cdot
H(\zeta)$ to the EMD objective in Equation 1. Approximating SNK via Sinkhorn
algorithm provably yields a $\varepsilon r$-additive approximation to EMD and
takes $O_{\varepsilon}(n^{2})$ time, where $r$ is the dataset diameter
[ANR17].

Graph-theoretic approaches also led to $\varepsilon r$-additive approximations
[LMR19] in $O_{\varepsilon}(n^{2})$ time. Notice that even though all previous
approximation algorithms have roughly the same complexity as the MCF-based
exact solution they are backed by experiments showing their practicality,
whereas exact algorithms for EMD are still largely impractical for very large
graphs.

#### Breaking the $O(n^{2})$ barrier.

In a recent paper Charikar et al.[Cha+23] write:

> _“There are no algorithmic approaches that achieve
> $(1\pm\varepsilon)$-approximations or $\varepsilon r$-additive
> approximations for either EMD nor SNK in time $n^{1.99}$. In addition, there
> is some reason to believe that this may be impossible for EMD [Roh19]”._

Both [AZ23] and our Theorem 1 disprove this conjecture. Indeed [AZ23] shows a
$(1+\varepsilon)$-multiplicative-approximation for Euclidean metrics, while
Theorem 1 provides an $\varepsilon$-additive approximation for general metrics
and both run in $n^{2-\Omega_{\varepsilon}(1)}$ time.

We stress that despite [AZ23] and this work proving similar results, they use
a completely different set of techniques. Indeed, in [AZ23] they approximate
the complete bipartite weighted graph induced by Euclidean distances with a
$(1+\varepsilon)$-multiplicative spanner of size
$n^{2-\Omega_{\varepsilon}(1)}$. Their spanner construction is based on LSH
and so it hinges on the Euclidean structure. Then, they run a near-linear time
MCF solver [Che+22] to solve the matching problem on the metric induced by the
spanner. In this work, instead, we build on sublinear algorithms for max-
cardinality matching [Beh22, Beh+23, BRR23, BKS23a, BKS23] and do not leverage
any metric property, not even triangle inequality. Section 2 contains a
detailed explanation of our techniques.

It is worth to notice that since [AZ23] operates over $d$-dimensional
Euclidean space the input representation takes $d\cdot n$ space, and so it
_does not_ run in sublinear time. On the contrary, our algorithm assumes query
access to the distance matrix and runs in sublinear time.

#### Sublinear algorithms.

Most previous work in sublinear models of computation focuses on streaming
Euclidean EMD [Che+22a, And+09, AIK08, Bac+20, Ind04, Cha02], where the latest
work [Che+22a] achieves $\tilde{O}(\log n)$-approximation in polylogarithmic
space. Some other work [Ba+11] addresses the sample complexity of testing
$\mathrm{EMD}$ on low-dimensional $\ell_{1}$.

In this work we focus on a different access model: we do not make any
assumption on the ground metric and we assume query access to the distance
matrix. This model is natural whenever the underlying metric is expensive to
evaluate. For example, in [ALT21] they consider EMD over a shortest-path
ground metric and experiment with heuristics to avoid computing all-pair
distances, which would be prohibitively expensive.

#### Comparison with MST.

Minimum Spanning Tree (MST) and EMD are two of the most studied optimization
problems in metric spaces. It is interesting to observe a separation between
the sublinear-time complexity of MST and EMD for general metrics. Indeed,
[CS09] shows a $\tilde{O}_{\varepsilon}(n)$ time algorithm approximating the
_cost_ of MST up to a factor $1+\varepsilon$, whereas no $O(1)$-approximation
for EMD can be computed in $o(n^{2})$ time [Băd+05]. Essentially, this is due
to the fact that MST cost is a more _robust_ problem than EMD. Indeed, in EMD
increasing a single entry in the distance matrix can increase the EMD
arbitrarily, whereas for MST this does not happen because of triangle
inequality.

A valuable take-home message from this work is that allowing additive
approximation makes EMD more robust. A natural question is whether we can find
a $\varepsilon$-additive approximation to EMD in $\tilde{O}_{\varepsilon}(n)$
time, thus matching the above result on MST cost. The $\Omega(n^{1.2})$ lower
bound on max-cardinality matching from [BRR23] suggests that this should not
be possible444The lower bound of [BRR23] is proven in a slightly different
model of adjacency list. Indeed, we can reduce max-cardinality matching to EMD
by embedding the bipartite graph into a $(1,2)$ metric space.

##  2 Technical Overview

Computing Earth Mover’s Distance between two sets of $n$ points in a metric
space can be achieved by solving Min-Weight Perfect Matching (MWPM) on the
complete bipartite graph where edge-costs are given by the metric
$d(\cdot,\cdot)$. Here we seek a suitable notion of approximation for MWPM
that recovers Theorem 1.

#### Min-weight perfect matching with outliers.

Consider the following problem: given a constant $\gamma>0$, find a matching
$M$ of size $(1-\gamma)n$ in a bipartite graph such that the cost of $M$ is at
most the minimum cost of a perfect matching. A natural interpretation of this
problem is to label a $\gamma$ fraction of vertices as outliers and leave them
unmatched; so we dub this problem MWPM _with outliers_.

Assuming $d(\cdot,\cdot)\in[0,1]$, solving MWPM with a $\gamma$ fraction of
outliers immediately yields a $\gamma$ additive approximation to EMD, proving
Theorem 1.

The main technical contribution of this work is the following theorem, which
introduces an algorithm that solves MWPM with outliers in sublinear time. For
the sake of this overview, the reader should instantiate Theorem 3 with
$\beta=1$ and think of $\gamma=(1-\alpha)$ as the fraction of allowed
outliers.

######  Theorem 3.

For each constants $0\leq\alpha<\beta\leq 1$ there exists a constant
$\varepsilon>0$ and an algorithm running in time $O(n^{2-\varepsilon})$ with
the following guarantees.

The algorithm has adjacency-matrix access to an undirected, bipartite graph
$G=(V_{0}\cup V_{1},E)$ and random access to the edge-cost function
$c:E\rightarrow\mathbb{R}^{+}$. The algorithm returns $\hat{c}$ such that,
whp,

$c(M^{\alpha})\leq\hat{c}\leq c(M^{\beta})$

where $M^{\alpha}$ is a minimum-weight matching of size $\alpha n$ and
$M^{\beta}$ is a minimum-weight matching of size $\beta n$.

Moreover, the algorithm returns a matching oracle data structure that, given a
vertex $u$ returns, in $n^{1+f(\varepsilon)}$ time, an edge $(u,v)\in\hat{M}$
or $\bot$ if $u\not\in V(\hat{M})$, where $f(\varepsilon)\rightarrow 0$ when
$\varepsilon\rightarrow 0$. The matching $\hat{M}$ satisfies $\alpha
n\leq|\hat{M}|\leq\beta n$ and $c(M^{\alpha})\leq c(\hat{M})\leq
c(M^{\beta})$.

Notice that the algorithm in Theorem 3 does not output the matching $\hat{M}$
explicitly. However, it returns a matching oracle data structure which
implicitly stores $\hat{M}$. The rest of this overview sketches the proof of
Theorem 3.

#### Our algorithm, in a nutshell.

A new set of powerful techniques was recently developed to approximate the
size of a max-cardinality matching in sublinear time [Beh22, Beh+23, BRR23,
BKS23a, BKS23]. Our main contribution is a sublinear-time algorithm which
leverages the techniques above to implement (a certain step of) the classic
Gabow-Tarjan [GT89] algorithm for MWPM. Since the techniques above return
_approximate_ solutions, the obtained matching will be approximate as well, in
the sense that we have to disregard a fraction of outliers when computing its
cost to recover a meaningful guarantee. Careful thought is required for
relaxing the definitions of certain objects in the Gabow-Tarjan algorithm so
as to accommodate their computation in sublinear time. The bulk of our
analysis is devoted to proving that these relaxations combine well and lead to
the guarantee in Theorem 3.

#### Roadmap.

First, we will review (a certain step of) the Gabow-Tarjan algorithm that we
will use as our template algorithm to be implemented in sublinear time. Then,
we will review some recent sublinear algorithms for max-cardinality matching.
Finally, we will sketch how to combine these tools to approximate the value of
minimum-weight matching.

###  2.1 A Template Algorithm

The original Gabow-Tarjan algorithm operates on several scales and this makes
it (slightly) more involved. We focus here on a simpler case where all our
edge weights are integers in $[1,C]$, for $C=O(1)$. We will see in Section 6
that we can reduce to this case (incurring a small additive error). Here we
describe our template algorithm, at a high level.

#### A linear program for MPWM.

First, recall the linear program for MWPM together with its dual. Here we
consider a bipartite graph $G(V=V_{0}\cup V_{1},E)$ and cost function
$c(\cdot,\cdot)\in[1,C]$. We can interpret the following LP so that
$x_{u,v}=1$ iff $u$ and $v$ are matched, whereas primal constraints require
every vertex to be matched.

Primal

Minimize $\displaystyle\sum_{u\in V_{0},v\in V_{0}}x_{u,v}\cdot c(u,v)$
subject to $\displaystyle\sum_{v\in V_{1}}x_{u,v}\geq 1\quad\forall u\in
V_{0}$ $\displaystyle\sum_{u\in V_{0}}x_{u,v}\geq 1\quad\forall v\in V_{1}$
$\displaystyle x_{u,v}\geq 0\quad\forall u\in V_{0},\;v\in V_{1}.$

Dual

Maximize $\displaystyle\sum_{u\in V}\varphi_{u}$ subject to
$\displaystyle\varphi_{u}+\varphi_{v}\leq c(u,v)\quad$
$\displaystyle\forall(u,v)\in E$ $\displaystyle\varphi_{u}\geq 0.\quad$
$\displaystyle\forall u\in V,$

#### A high-level description.

Essentially, our template algorithm is a primal-dual algorithm which
(implicitly) maintains a pair $(M,\varphi)$, where $M$ is a partial matching
(so primal infeasible), and $\\{\varphi(v)\\}_{v\in V}$ is a vertex potential
function, or an (approximately) feasible dual solution. Moreover, for each
$e\in M$ the dual constraint corresponding to $e$ is tight. In other words,
the pair $(M,\varphi)$ satisfies complementary slackness. The algorithm
progressively grows the dual variables $\\{\varphi(v)\\}_{v\in V}$ and the
size of $M$. When $M$ has size $\geq(1-\gamma)n$ then we are done. Indeed,
throwing out $\gamma n$ vertices (as well as their associated primal
constraints) we have that $(M,\varphi)$ is a (approximately) feasible primal-
dual pair that satisfies complementary slackness, thus it is (approximately)
optimal.

#### The primal-dual algorithm.

We maintain an initially empty matching $M$. Inspired by the dual, we define a
potential function $\varphi:V\rightarrow\mathbb{Z}$ and we enforce a relaxed
version of the dual constraints: $\varphi(u)+\varphi(v)\leq c(u,v)+1$ for each
$(u,v)\in E$. Moreover, we maintain that $\varphi(u)+\varphi(v)=c(u,v)$ for
each $(u,v)\in M$ (complementary slackness). Let $T$ be the set of edges s.t.
the constraints above are tight. Orient the edges in $T$ so that all edges in
$M\subseteq T$ are oriented from $V_{0}$ to $V_{1}$ and all edges in
$T\setminus M$ are oriented from $V_{1}$ to $V_{0}$. We denote the set of free
(unmatched) vertices $F$ and let $F_{0}=F\cap V_{0}$ $F_{1}=F\cap V_{1}$. We
say that a path $P=(v_{0}\rightarrow\cdots\rightarrow v_{1})$ is an augmenting
path if $v_{0}\in F_{0}$, $v_{1}\in F_{1}$ and $P$ alternates between edges in
$T\setminus M$ and $M$. When we say that we augment $M$ wrt $P$ we mean that
we set $M\leftarrow M\oplus P$. We alternate between the following two steps:

  1. 1.

Find a a large set of node-disjoint augmenting paths $\\{P_{1}\dots
P_{\ell}\\}$. Augment $M$ wrt these paths. Decrement $\varphi(v)\texttt{ -=
}1$ for each $v\in\bigcup_{i}P_{i}\cap V_{1}$, to ensure the relaxed dual
constraints are satisfied.

  2. 2.

Define $R$ as the set of vertices that are $T$-reachable555Recall that $T$ is
oriented. from $F_{0}$. Increment $\varphi(r_{0})\texttt{ += }1$ for each
$r_{0}\in R\cap V_{0}$, and decrement $\varphi(r_{1})\texttt{ -= }1$ for each
$r_{1}\in R\cap V_{1}$. This preserves the relaxed dual constraints and
(eventually) adds some more edges to $T$.

After $O_{\gamma,C}(1)$ iterations, we have $|F|\leq\gamma n$.

#### Analysis sketch.

It is routine to verify that steps 1 and 2 preserve the relaxed dual
constraints. At any point the pair $(M,\varphi)$ satisfies,
$c(M)\leq\sum_{v\in V_{0}\cup V_{1}}\varphi(v)\leq c(M^{\prime})+n$ for any
perfect matching $M^{\prime}$. We can content ourselves with this additive
approximation; indeed in Section 6 we will see how to charge it on the
outliers. To argue that we have few free vertices left after $O_{\gamma}(1)$
iterations, notice that at iteration $t$ we have $\varphi|_{F_{0}}\equiv t$
and $\varphi|_{F_{1}}\equiv 0$. Computing a certain function of potentials
along $(M\oplus M^{\prime})$-augmenting paths shows that $|F|\cdot t\leq
O(n)$. Thus, $O_{\gamma}(1)$ iterations are sufficient to obtain
$|F|\leq\gamma n$. The arguments above are sufficient to show that our
template algorithm finds an (almost) perfect matching with (almost) minimum
weight. We will shove both _almost_ under the outlier carpet in Section 6.

###  2.2 Implementing the Template in Sublinear Time

Our sublinear-time implementation of the template algorithm hinges on matching
oracles.

#### Matching oracles.

Given a matching $M^{\prime}$ we define a _matching oracle_ for $M^{\prime}$
as a data structure that given $u\in V$ returns $v\in V$ if $(u,v)\in
M^{\prime}$ and $\bot$ otherwise. Note that given a matching oracle for
$M^{\prime}$, if we are promised that $|M^{\prime}|=\Omega(n)$ then
$O_{\gamma}(\log n)$ calls to such oracle are enough to estimate
$|M^{\prime}|\pm\gamma n$. We stress that all matching oracles that we use
have sublinear query time.

#### Finding large matchings in sublinear time.

An important ingredient in our algorithm is the
$\texttt{LargeMatching}(G,A,\varepsilon,\delta)$ subroutine (Theorem 5), which
is due to [BKS23]. Given $A\subseteq V$,
$\texttt{LargeMatching}(G,A,\varepsilon,\delta)$ returns either $\bot$ or a
matching oracle for some matching $M^{\prime}$ in $G[A]$. If there exists a
matching in $G[A]$ of size $\delta n$, then LargeMatching returns a matching
oracle for some $M^{\prime}$ in $G[A]$ with $|M^{\prime}|=\Omega_{\delta}(n)$.
Else, if there are no matchings of size $\delta n$ in $G[A]$ LargeMatching
returns $\bot$. The parameter $\varepsilon$ controls the running time and
essentially guarantees that LargeMatching runs in $O(n^{2-\varepsilon})$ time
while the matching oracle it outputs runs in $O(n^{1+\varepsilon})$.

We will use LargeMatching to implement both step 1 and step 2 in the template
algorithm. However, this requires us to relax our notions of maximal set of
node-disjoint augmenting paths, as well as that of reachability. A major
technical contribution of this work is to find the right relaxation of these
notions so that:

  1. 1)

We can analyze a variant of the template algorithm working with these relaxed
objects and still recover a a solution which is optimal if we neglect a
$\gamma$ fraction of outliers.

  2. 2)

We can compute these relaxed objects in sublinear time using LargeMatching as
well as previously constructed matching oracles.

These relaxed notions are introduced in Section 3, point (1) is proven in
Section 4 and point (2) is proven in Section 5.

#### Implementing step 1 in sublinear time.

In [BKS23] the authors implement McGregor’s algorithm [McG05] for streaming
Max-Cardinality Matching (MCM) in a sublinear fashion using LargeMatching (see
Theorem 6 in this work). McGregor’s algorithm finds a size-$\Omega(n)$ set of
node-disjoint augmenting paths of fixed constant length, whenever there are at
least $\Omega(n)$ of them. This notion is weaker than that of a maximal node-
disjoint set of augmenting paths required in step 1 of our template algorithm
in two regards: first, it only finds augmenting paths of fixed constant
length; second, it finds only a constant fraction of such paths (as long as we
have a linear number of them).

In our template algorithm, the invariant $\varphi|_{F_{1}}\equiv 0$ is
maintained (in step 2) because $R\cap F_{1}=\emptyset$. In turn, $R\cap
F_{1}=\emptyset$ holds exactly because in step 1 we augment $M$ with a maximal
node-disjoint set of augmenting paths. Since our sublinear implementation of
step 1 misses some augmenting paths, the updates performed in step 2 will
violate the invariant $\varphi(v)=0$ for some $v\in F_{1}$.

A careful implementation of step 2 (see next paragraph) guarantees that only
missed augmenting paths that are short lead to a violation of
$\varphi|_{F_{1}}\equiv 0$. Moreover, repeatedly running the sublinear
implementation of McGregor’s algorithm from [BKS23], we ensure that we miss at
most $\gamma n$ short paths, for $\gamma$ arbitrary small. Thus, we can flag
all vertices that belong to missed short augmenting paths as outliers since we
have only a small fraction of them.

#### Implementing step 2 in sublinear time.

We implement an approximate version of the reachability query in step 2 as
follows. We initialize the set of reachable vertices $R$ as $R\leftarrow
F_{0}$. Then, for a constant number of iterations: we compute a large matching
$M^{\prime}\subseteq T\setminus M$ between the vertices of $R\cap V_{0}$ and
$V_{1}\setminus R$; then we add to $R$ all matched vertices in $\bigcup
M^{\prime}$ as well as their $M$-mates, namely $\mathtt{mate}_{M}(u)$ for each
$u\in\bigcup M^{\prime}$. Notice that if a $\Omega(n)$-size matching
$\subseteq T\setminus M$ between $R\cap V_{0}$ and $V_{1}\setminus R$ exists,
then we find a matching $\subseteq T\setminus M$ between $R\cap V_{0}$ and
$V_{1}\setminus R$ of size at least $\Omega(n)$. This ensures that: (i) after
a constant number of iterations LargeMatching returns $\bot$; (ii) when
LargeMatching returns $\bot$ there exists a vertex cover $\mathcal{C}$ of
$((R\cap V_{0})\times(V_{1}\setminus R))\cap T\setminus M$ of size $\gamma n$.
Only constraints corresponding to edges incident to $\mathcal{C}$ might be
violated during step 2. Furthermore, $|\mathcal{C}|=\gamma n$ is small and so
we can just label vertices in $\mathcal{C}$ as outliers.

As we pointed out in the previous paragraph, the invariant
$\varphi|_{F_{1}}\equiv 0$ might be violated in step 2 if $R\cap
F_{1}\neq\emptyset$. We already showed that whenever we the missed augmenting
path causing the violation of $\varphi|_{F_{1}}\equiv 0$ is short we can
charge this violation on a small set of outliers. To make sure that no long
augmenting path leads to a violation of $\varphi|_{F_{1}}\equiv 0$ we set our
parameters so that the depth of the reachability tree built in step 2 is
smaller than the length of “long” paths. Thus, any long path escapes $R$ and
cannot cause a violation.

#### Everything is an oracle.

The implementation of both step 1 and step 2 operates on the graph $T$ of
tight constraints. To evaluate $(u,v)\in T$, we need to compute $\varphi(u)$
and $\varphi(v)$. In turn, the potential values depend on previous iterations
of the algorithm. None of these iterations outputs an explicit description of
the objects described in the template (potentials, matchings, augmenting paths
or sets of reachable vertices). Indeed, these objects are output as oracle
data structures, which internals call (eventually multiple) matching oracles
output by LargeMatching. We prove that essentially all these oracles have
query time $O(n^{1+\varepsilon})$ for some small $\varepsilon>0$. A careful
analysis is required to show that we can build the oracles at iteration $i+1$
using the oracles at iteration $i$ without blowing up their complexity.

#### Paper organization.

In Section 3 we define some fundamental objects that we will use throughout
the paper. In Section 4 we present a template algorithm to be implemented in
sublinear time, and prove its correctness. In Section 5 we implement the
template algorithm in sublinear time. In Section 6 we put everything together
and prove the main theorems stated in the introduction.

##  3 Preliminaries

We use the notation $[a,b]:=\\{a\dots b-1\\}$, $[b]=[0,b]$, and $(a\pm
b):=[a-b,a+b]$ meaning that $c\cdot(a\pm b)=(ac\pm bc)$. We denote our
undirected bipartite graph with $G=(V,E)$, and the bipartition is given by
$V=V_{0}\cup V_{1}$. Our original graph is complete and for each $(u,v)\in
V_{0}\times V_{1}$ we denote with $c(u,v)$ the cost of the edge $(u,v)$. We
stress that none of our algorithms require $c(\cdot,\cdot)$ to be a metric.
Given a matching $M$ we denote its combined cost with $c(M)$. For each $u\in
V$ we say that $u=\mathtt{mate}_{M}(v)$ iff $(u,v)\in M$. When the matching
$M$ is clear from the context we denote with $F$ the set of unmatched (or
_free_) vertices, and set $F_{i}:=F\cap V_{i}$ for $i=0,1$.

When we say that an algorithm runs in time $t$ we mean that both its
computational complexity and the number of queries to the cost matrix
$c(\cdot,\cdot)$ are bounded by $t$. The computational complexity of our
algorithms is always (asymptotically) equivalent to their query complexity, so
we only analyse the latter. All our guarantees in this work hold with high
probability.

######  Definition 3.1 (Augmenting paths).

Given a matching $M$ over $G=(V,E)$ we say that $P=(v_{0},v_{1}\dots
v_{2\ell+1})$ is an augmenting path w.r.t. $M$ if $(v_{2i},v_{2i+1})\in
E\setminus M$ for each $i=0\dots\ell$ and $(v_{2j+1},v_{2j+2})\in M$ for each
$j=0\dots\ell-1$. When we say that we augment $M$ w.r.t. $P$ we mean that we
set $M\leftarrow M\oplus P$, where $\oplus$ is the exclusive or.

We use the same notion of $1$-feasible potential as in [GT89].

######  Definition 3.2 ($1$-feasibility conditions).

Given a potential $\varphi:V\longrightarrow\mathbb{Z}$ we say that it
satisfies $1$-feasibility conditions with respect to a matching $M$ if the
following hold.

  1. (i)

For each $u\in V_{0},v\in V_{1}$ $\varphi(u)+\varphi(v)\leq c(u,v)+1$.

  2. (ii)

For each $(u,v)\in M$, $\varphi(u)+\varphi(v)=c(u,v)$.

######  Definition 3.3 (Eligibility Graph).

We say that an edge $(u,v)$ is eligible w.r.t. $M$ if: $(u,v)\not\in M$ and
$\varphi(u)+\varphi(v)=c(u,v)+1$ or; $(u,v)\in M$ and
$\varphi(u)+\varphi(v)=c(u,v)$. We define the eligibility graph as the
directed graph $G_{\mathcal{E}}=(V,E_{\mathcal{E}})$ that orients the eligible
edges so that, for each eligible $(u,v)\in V_{0}\times V_{1}$, we have
$(u,v)\in E_{\mathcal{E}}$ if $(u,v)\not\in M$ and $(v,u)\in E_{\mathcal{E}}$
if $(u,v)\in M$.

Notice that, whenever a potential is $1$-feasible w.r.t. $M$, then all edges
in $M$ are eligible.

######  Definition 3.4 (Forward Graph).

We define the forward graph $G_{F}=(V,E_{F})$ as the subgraph of the
eligibility graph containing only edges from $V_{0}$ to $V_{1}$. That is, we
remove all edges $(v,u)$ such that $(u,v)\in M$.

Now, we introduce two quite technical definitions, which provide us with
approximate versions of the notion of “maximal set of node-disjoint augmenting
paths” and “maximal forest”.

######  Definition 3.5 ($(k,\xi)$-Quasi-Maximal Set of Node-Disjoint
Augmenting Paths).

Given a graph $G=(V,E)$ and a matching $M\subseteq E$ we say that a set
$\mathcal{P}$ of augmenting paths of length at most $k$ is a $(k,\xi)$-QMSNDAP
if for any $\mathcal{Q}$ such that $\mathcal{Q}\cup\mathcal{P}$ is a set of
node-disjoint augmenting paths of length $\leq k$ we have
$|\mathcal{Q}|\leq\xi n$.

Intuitively, $\mathcal{P}$ is a $(k,\xi)$-QMSNDAP if we can add only a few
more node-disjoint augmenting paths of length $\leq k$ to $\mathcal{P}$ before
it becomes a maximal. Next we introduce an approximate notion of “maximal
forest” $\mathcal{F}$ in the eligibility graph $G_{\mathcal{E}}$ rooted in
$F_{0}$. $\mathcal{F}$ is obtained starting from the vertices in $F_{0}$ and
adding edges (in a way that we will specify later) so as to preserve the
$\mathcal{F}$ has $|F_{0}|$ connected components and has no cycles. This
construction will ensure that the connected component of our forest have small
diameter and small size. We maintain that whenever $v\in V_{1}$ is added to
$\mathcal{F}$, then $\mathtt{mate}_{M}(v)$ is also added to $\mathcal{F}$.
$\mathcal{F}$ is approximately maximal in the sense that the cut
$(\mathcal{F},V\setminus\mathcal{F})$ in $G_{\mathcal{E}}$ admits a small
vertex cover.

######  Definition 3.6 ($(k,\delta)$-Quasi-Maximal Forest).

Given the eligibility graph $G_{\mathcal{E}}=(V,E_{\mathcal{E}})$ w.r.t. the
matching $M$, and the set of vertices $F_{0}\subseteq V_{0}$ we say that
$\mathcal{F}$ is a $(k,\delta)$-QMF rooted in $F_{0}$ if:

  1. 1.

$F_{0}\subseteq\mathcal{F}$

  2. 2.

For each $v\in V_{1}\cap\mathcal{F}$ we have
$\mathtt{mate}_{M}(v)\in\mathcal{F}$

  3. 3.

For each $u\in\mathcal{F}$ there exists $v\in F_{0}$ at hop distance from $u$
at most $k$.

  4. 4.

Every connected component of $\mathcal{F}$ has size at most $2^{k}$.

  5. 5.

The edge set $E_{\mathcal{E}}\cap(\mathcal{F}\times V\setminus\mathcal{F})$
has a vertex cover of size at most $\delta n$.

Now, we introduce a few results from past work on sublinear-time maximum
caridnality matching. The following theorem, which is the main technical
contribution of [BKS23], states that we can compute a $\varepsilon n$-additive
approximation of the size of a maximum-cardinality matching in strongly
sublinear time.

######  Theorem 4 (Theorem 1.3, [BKS23]).

There is a randomized algorithm that, given the adjacency matrix of a graph
$G$, in time $n^{2-\Omega_{\varepsilon}(1)}$ computes with high probability a
$(1,\varepsilon n)$-approximation $\tilde{\mu}$ of $\mu(G)$. After that, given
a vertex $v$, the algorithm returns in $n^{1+f(\varepsilon)}$ time an edge
$(v,v^{\prime})\in M$ or $\bot$ if $v\notin V(M)$ where $M$ is a fixed
$(1,\varepsilon n)$-approximate matching, where $f$ is an increasing function
such that $f(\varepsilon)\rightarrow 0$ when $\varepsilon\rightarrow 0$.

The algorithm in Theorem 4 does not exactly output a matching, but rather a
_matching oracle_. Namely, it outputs a data structure that stores a matching
$M$ implicitly. We formalize the notion of matching oracle below.

######  Definition 3.7 (Matching Oracle).

Given a matching $M$, we define the matching oracle
$\mathtt{match}_{M}(\cdot)$ as a data structure such that
$\mathtt{match}_{M}(u)=v$ if $(u,v)\in M$ and $\mathtt{match}_{M}(u)=\bot$
otherwise. Throughout the paper we denote with $t_{M}$ the time complexity of
$\mathtt{match}_{M}(\cdot)$.

Similarly to matching oracles, we make use of membership oracles
$\mathtt{mem}_{A}(\cdot)$ and potential oracles
$\mathtt{eval}_{\varphi}(\cdot)$ where $A\subseteq V$ and $\varphi$ is a
potential function defined on $V$. As expected, $\mathtt{mem}_{A}(u)$ returns
$\mathbbm{1}_{u\in A}$ and $\mathtt{eval}_{\varphi}(u)$ returns $\varphi(u)$.
We denote their running time with $t_{A}$ and $t_{\varphi}$ respectively. Now,
we recall two theorems from [BKS23] that constitutes fundamental ingredients
of our sublinear-time algorithm for minimum-weight matching.

Theorem 5 roughly says that, in sublinear time, we can find a matching oracle
for a size-$\Omega(n)$ matching, whenever a size-$\Omega(n)$ matching exists.

######  Theorem 5 (Essentially Theorem 4.1, [BKS23]).

Let $G=(V,E)$ be a graph, $A\subseteq V$ be a vertex set. Suppose that we have
access to adjacency matrix of $G$ and an $A$-membership oracle
$\mathtt{mem}_{A}$ with $t_{A}$ query time. We are given as input a
sufficiently small $\varepsilon>0$ and $\delta_{\mathrm{in}}>0$.

There exists an algorithm
$\texttt{LargeMatching}(G,A,\varepsilon,\delta_{\mathrm{in}})$ that
preprocesses $G$ in $\tilde{O}_{\delta_{\mathrm{in}}}((t_{A}+n)\cdot
n^{1-\varepsilon})$ time and either return $\bot$ or construct a matching
oracle $\mathtt{match}_{M}(\cdot)$ for a matching $M\subset G[A]$ of size at
least $\delta_{\mathrm{out}}n$ where
$\delta_{\mathrm{out}}=\frac{1}{2000}\delta_{\mathrm{in}}^{5}$ that has
$\tilde{O}_{\delta_{\mathrm{in}}}((t_{A}+n)n^{4\varepsilon})$ worst-case query
time. If $\mu(G[A])\geq\delta_{\mathrm{in}}n$, then $\bot$ is not returned.
The guarantee holds with high probability.

Theorem 6 roughly says that, in sublinear time, we can increase the size of
our current matching (oracle) by $\Omega(n)$, whenever there are $\Omega(n)$
short augmenting paths.

######  Theorem 6 (Essentially Theorem 5.2, [BKS23]).

Fix two constants $k,\gamma>0$. For any sufficiently small
$\varepsilon_{\texttt{in}}>0$, there exists
$\varepsilon_{\texttt{out}}=\Theta_{k,\gamma}(\varepsilon_{\texttt{in}})$ such
that the following holds. There exists an algorithm
$\texttt{Augment}(G,M^{\texttt{in}},k,\gamma,\varepsilon_{\texttt{in}})$ that
makes $O_{k,\gamma}(1)$ calls to LargeMatching which take
$\tilde{O}_{k,\gamma}\left(n^{2-\varepsilon_{\texttt{in}}}\right)$ time in
total. Further, either it returns an oracle
$\mathtt{match}_{M^{\texttt{out}}}(\cdot)$ with query time
$\tilde{O}_{k,\gamma}(n^{1+\varepsilon_{\texttt{out}}})$, for some matching
$M^{\texttt{out}}$ in $G$ of size
$|M^{\texttt{out}}|\geq|M^{\texttt{in}}|+\Theta_{k,\gamma}(1)\cdot n$ (we say
that it “succeeds” in this case), or it returns Failure. Finally, if the
matching $M^{\texttt{in}}$ admits a collection of $\gamma\cdot n$ many node-
disjoint length $(2k+1)$-augmenting paths in $G$, then the algorithm succeeds
whp.

Theorem 6 differs from Theorem 5.2 in [BKS23] in that it specifies that the
only way Augment accesses the graph is through LargeMatching. We will use this
property crucially to prove Lemma 5.2.

##  4 A Template Algorithm

In this section we study min-weight matching with integral small costs
$c(\cdot,\cdot)\in[1,C]$, where $C$ is constant. We will see how to lift this
restriction in Section 6. Algorithm 1 gives a template algorithm realising
Theorem 3 that assumes we can implement certain subroutines; in Section 5 we
will see how to implement these subroutines in sublinear time.

#### Comparison with Gabow-Tarjan.

Intuitively, our template algorithm implements the Gabow-Tarjan algorithm
[GT89] for a fixed scale in an approximate fashion. Indeed, instead of finding
a maximal-set of node-disjoint augmenting paths we find a $(k,\xi)$-QMSNDAP
and instead of growing a forest in the eligibility graph we grow a
$(k,\delta)$-QMF. See Figure 1 for a representation of step 1 and step 2.

Input: A bipartite graph $G=(V_{0}\cup V_{1},E)$ and a cost function
$c:E\rightarrow[1,C]$.

Set $T=C/\gamma^{3}$, $\xi=\frac{\gamma}{Tk2^{k}}$, $\delta=\frac{\gamma}{T}$
and $k=6000(2T+1)^{10}/\delta^{5}$.

Initialize $M\leftarrow\emptyset$ and $\varphi(v)\leftarrow 0$ for each $v\in
V$.

Let $F_{0}$ denote the set of $M$-unmatched vertices in $V_{0}$.

For each $e\in E$ update $c(e)\leftarrow c(e)/\gamma$ (this is implemented
lazily).

Execute the following two steps for $T$ iterations:

  * •

Step 1. Find a $(k,\xi)$-QMSNDAP $\mathcal{P}$ in the eligibility graph
$G_{\mathcal{E}}$. Augment $M$ w.r.t. paths in $\mathcal{P}$. Set
$\varphi(v)\leftarrow\varphi(v)-1$ for each $v\in
V_{1}\cap\bigcup_{P\in\mathcal{P}}P$.

  * •

Step 2. Find a $(k,\delta)$-QMF$\mathcal{F}$ rooted in $F_{0}$ in the
eligibility graph $G_{\mathcal{E}}$. Set $\varphi(u)\leftarrow\varphi(u)+1$
for each $u\in V_{0}\cap\mathcal{F}$ and $\varphi(v)\leftarrow\varphi(v)-1$
for each $v\in V_{1}\cap\mathcal{F}$.

Sample a set $S$ of $O_{\gamma,C}(\log n)$ edges in $M$ with replacement.

Discard the $3\gamma|S|$ edges with highest costs and let $\Sigma$ be the sum
of costs of remaining edges.

Output: $\hat{c}=\frac{n}{|S|}\Sigma$.

Algorithm 1 Template Algorithm.

Figure 1:  We color the edges of $M$ in red and the edges of $T\setminus M$ in
blue. On the left we have an example of step 1. Solid edges represent paths in
the QMSNDAP $\mathcal{P}$ that we augment $M$ along in step 1. On the right we
have an example of step 2. All vertices colored or circled in green belong to
the QMF $\mathcal{F}$. Circles help us visualize the implementation of step 2,
described in Section 5. In Algorithm 3 $\mathcal{F}$ is built sequentially,
where each iteration (lines 1-5) adds some edges to $\mathcal{F}$. At first,
only the non-circled green vertices belong to $\mathcal{F}$. The first step
adds the green-circled black edges, and the second step adds the green-circled
green edges.

#### Analysis.

Here we analyse Algorithm 1 and show that it satisfies the following theorem.

######  Theorem 7.

Fix a constant $\gamma>0$. Suppose that we have adjacency-matrix access to the
bipartite graph $G=(V_{0}\cup V_{1},E)$ and random access to the cost function
$c:E\rightarrow[1,C]$, with $C=O(1)$. Then, with high probability, Algorithm 1
returns $\hat{c}$ such that

$c(M^{1-\gamma})\leq\hat{c}\leq c(M^{\texttt{OPT}})$

where $M^{1-\gamma}$ is a min-weight matching of size $(1-\gamma)n$ and
$M^{\texttt{OPT}}$ is a min-weight matching of size $n$.

To prove Theorem 7, we need a series of technical lemmas.

#### Proof Roadmap.

The proof of Theorem 7 goes as follows. We prove that, after $T$ iterations,
all free vertices in $F_{0}$ have potential $T$. On the other hand, the
majority of free vertices in $F_{1}$ have potential $0$. We call _spurious_
the free vertices in $F_{1}$ with non-zero potential and we show there are
only few of them. Then, (roughly) we look at the final matching $M$ generated
by Algorithm 1 and a perfect matching $M^{\prime}$ and consider the graph
$G^{\prime}$ having $M\oplus M^{\prime}$ as its set of edges. $G^{\prime}$ can
be partitioned into cycles and augmenting paths. Each augmenting path starts
in a free vertex in $F_{0}$ and ends in a free vertex in $F_{1}$. If the
$1$-feasibility conditions are satisfied by all edges, then computing a
certain function of potentials along an augmenting path and combining the
results for all augmenting paths yields an upper bound on the total number of
free vertices. Unfortunately, not all edges satisfy the $1$-feasibility
constraints. We fix this by finding a small vertex cover of the $1$-unfeasible
edges. We say that such cover a suitable set of _broken_ vertices. Ignoring
spurious and broken vertices is sufficient to make our argument work.

######  Lemma 4.1.

After $t\in[T+1]$ iterations we have $\varphi(u)=t$ for each $u\in F_{0}$.

###### Proof.

After $t=0$ iterations, we have $\varphi(u)=0$ for each $u\in V$. First, we
notice that the set of unmatched (or free) vertices $F$ only shrinks over
time, and so does $F_{0}$. Moreover, at each iteration we increase the
potential of free vertices in $F_{0}$ by $1$. ∎

Define the set $S$ of $v\in F_{1}$ such that $\varphi(v)\neq 0$ as the set of
_spurious_ vertices.

######  Lemma 4.2.

After $T$ iterations we have at most $\gamma n$ _spurious_ vertices.

###### Proof.

We prove that at each iteration we increase the number of spurious vertices by
at most $\gamma n/T$. A vertex cannot become spurious in Step 1. Indeed, in
Step 1 we only decrease the potential of matched vertices. If a vertex $v\in
F_{1}$ becomes spurious in Step 2, it means that there exists an augmenting
path $P$ from some $u\in F_{0}$ to $v$ contained in a connected component of
$\mathcal{F}$. Let $\mathcal{Q}$ be such that $\mathcal{Q}\cup\mathcal{P}$ is
a maximal set of node-disjoint augmenting paths of length $\leq k$. By
Definition 3.5 we have $|\mathcal{Q}|\leq\xi n$. Define the set of _forgotten_
vertices as $\bigcup_{Q\in\mathcal{Q}}Q$. Thanks to item 3 in Definition 3.6,
the path from $u$ to $w$ has length $\leq k$, thus $P$ has length at most $k$.
Recall that $P$ is an augmenting path w.r.t. the graph obtained augmenting $M$
along $\mathcal{P}$ at the end of Step 1. Therefore, $P$ intersects a path in
$\mathcal{Q}\cup\mathcal{P}$.

We now argue that that $P$ cannot intersect $P^{\prime}\in\mathcal{P}$.
Suppose by contradiction that it does. Let $P=(P_{0}\dots P_{\ell})$ and
$P^{\prime}=(P^{\prime}_{0}\dots P^{\prime}_{\ell^{\prime}})$. Let $P_{s}$ be
the first (w.r.t. the order induced by $P$) node where $P$ and $P^{\prime}$
intersect. We first rule out the case that $s$ is even: for $s=0$, $P_{0}=u\in
F_{0}$ implies that $u$ did not belong to an augmenting path $P^{\prime}$ in
Step 1. Moreover, for $s=2i>0$ if $P_{2i}=P^{\prime}_{j}$ then
$P_{2i-1}=\mathtt{mate}_{M}(P_{2i})\in\\{P^{\prime}_{j-1},P^{\prime}_{j+1}\\}$,
where $M$ is the matching obtained at the end of Step 1. Now suppose that $s$
is odd, and hence $P_{s}\in V_{1}\cap P^{\prime}$. Then $\varphi(P_{s})$ is
decreased by $1$ at the end of Step 1, hence no edge outside of $M$ incident
to $P_{s}$ is eligible in Step 2.

Thus, $P$ must intersect a path in $\mathcal{Q}$. On the other hand
$\bigcup_{Q\in\mathcal{Q}}Q$ contains at most $k\xi n$ vertices, so at most
$k\xi n$ connected component of $\mathcal{F}$ contain a forgotten edge.
Moreover, by item 4 of Definition 3.6 every connected component of
$\mathcal{F}$ has size at most $2^{k}$, thus at most $k\xi n2^{k}=\gamma/T$
vertices become spurious. ∎

We say that $B\subseteq V$ is a suitable set of _broken_ vertices if all
$(u,v)\in(V_{0}\setminus B)\times(V_{1}\setminus B)$ are $1$-feasible.

######  Lemma 4.3.

After $T$ iterations, there exists a suitable set of broken vertices of size
at most $\gamma n$.

###### Proof.

First, we prove that every edge $(u,v)\in V_{0}\times V_{1}$, which is
$1$-feasible at the beginning of Step 1, is also $1$-feasible at the end of
Step 1. Suppose that $(u,v)$ becomes $1$-unfeasible in Step 1. Let $M$ and
$M^{\prime}$ be the matching at the beginning and at the end of Step 1
respectively. Potentials only decrease in Step 1, so in order for $(u,v)$ to
become $1$-unfeasible w.r.t. $M^{\prime}$ we must have $(u,v)\in M^{\prime}$.
Moreover, we decrease the potential of $v$ only if $(u,v)\in P$, for some
augmenting path $P$. Thus, at the beginning of Step 1 we had
$\varphi(u)+\varphi(v)=c(u,v)+1$, which implies $\varphi(u)+\varphi(v)=c(u,v)$
at the end of Step 1, thus $(u,v)$ is $1$-feasible w.r.t. $M^{\prime}$,
contradiction.

Now, we grow a set of suitable broken vertices $B$. We initialize
$B=\emptyset$ and show that each iteration Step 2 increases the size of $B$ by
at most $\gamma n/T$. If $(u,v)\in V_{0}\times V_{1}$ is $1$-feasible at the
beginning of Step 2 and becomes $1$-unfeasible in Step 2, then we must have
$u\in\mathcal{F}$ and $v\not\in\mathcal{F}$. Indeed, by item 2 in Definition
3.6 if $(u,v)\in M^{\prime}$ then either both $u$ and $v$ belong to
$\mathcal{F}$ or neither of them does. This ensures that the sum of their
potentials is unchanged. Else, if $(u,v)\not\in M^{\prime}$ then in order for
it to violate $1$-feasibility we must increase $\varphi(u)$ by one and not
decrease $\varphi(v)$, and this happens only if $u\in\mathcal{F}$ and
$v\not\in\mathcal{F}$. Item 5 in Definition 3.6 ensures that there exists a
vertex cover $U\subseteq V$ for the set of new $1$-unfeasible edges with
$|U|\leq\delta n=\gamma n/T$. We update $B\leftarrow B\cup U$. Thus, after $T$
iterations we have $|B|\leq\gamma n$. ∎

######  Lemma 4.4.

After $T$ iterations of template algorithm we have have $|F_{0}|=|F_{1}|\leq
4\gamma n$.

###### Proof.

Denote with $M$ the final matching obtained by Algorithm 1. Let $B$ be a
suitable set of broken vertices with $|B|\leq\gamma n$, as in Lemma 4.3.
Partition $B=B_{M}\cup B_{F}$, where $B_{F}:=B\cap F$ is the set of unmatched
vertices in $B$ and $B_{M}$ is the set of matched vertices in $B$. Consider
the set $B^{\prime}_{M}$ of vertices currently matched to vertices in $B_{M}$,
$B^{\prime}_{M}=\\{\mathtt{mate}_{M}(b)\;|\;b\in B_{M}\\}$. We have
$|(B_{M}\cup B^{\prime}_{M})\cap V_{0}|=|(B_{M}\cup B^{\prime}_{M})\cap
V_{1}|\leq\gamma n$. Let $S$ be the set of spurious vertices and recall that
$|S|\leq\gamma n$ by Lemma 4.2. Let $S^{\prime}\subseteq F_{0}\setminus B_{F}$
such that $|S^{\prime}\cup(V_{0}\cap B_{F})|=|S\cup(V_{1}\cap B_{F})|$. This
implies that $|S^{\prime}\cup(V_{0}\cap B_{F})|\leq|S|+|B|\leq 2\gamma n$.
Define $A_{0}:=V_{0}\setminus(B\cup B^{\prime}_{M}\cup S^{\prime})$ and
$A_{1}:=V_{1}\setminus(B\cup B^{\prime}_{M}\cup S)$ and notice that they have
the same size. Define $A=A_{0}\cup A_{1}$. Let $M^{\prime}$ be a perfect
matching over $A$.

The graph $G_{A}=(A,M\oplus M^{\prime})$ contains exactly $\ell:=|F_{0}\cap
A_{0}|=|F_{1}\cap A_{1}|$ node-disjoint paths $P_{1}\dots P_{\ell}$ where
$P_{i}$ starts in $f^{(i)}_{0}\in F_{0}\cap A_{0}$ and ends in $f_{1}^{(i)}\in
F_{1}\cap A_{1}$. We define the _value_ of a path $P$ as

$\mathcal{V}(P)=\sum_{(u,v)\in M^{\prime}\cap
P}\left(c(u,v)+1\right)-\sum_{(u,v)\in M\cap P}c(u,v).$

By $1$-feasibility of $\varphi$ we have

$\mathcal{V}(P_{i})\geq\sum_{(u,v)\in M^{\prime}\cap
P}\left(\varphi(u)+\varphi(v)\right)-\sum_{(u,v)\in M\cap
P}(\varphi(u)+\varphi(v))=\varphi\left(f^{(i)}_{0}\right)-\varphi\left(f_{1}^{(i)}\right)=T$

where the last equality holds by definition of (non-)spurious vertices and
Lemma 4.1. Then, we have $Cn\geq
n+c(M^{\prime})\geq\sum_{i}^{\ell}\mathcal{V}(P_{i})\geq\ell T$. Thus,
$\ell\leq Cn/T=\gamma n$ and

$|F_{1}|=|F_{0}|\leq|F_{0}\cap A|+|(B_{M}\cup B^{\prime}_{M})\cap
V_{0}|+|S^{\prime}\cup(V_{0}\cap B_{F})|\leq 4\gamma n.$

∎

Let $\varphi$ be the potential at the end of the execution of Algorithm 1.
Denote with $M^{\texttt{ALG}}$ the final matching obtained by Algorithm 1 and
with $M^{\texttt{OPT}}$ a min-weight perfect matching. Given a matching $M$,
we denote with $M_{[\alpha]}$ the matching obtained from $M$ by removing the
$\alpha n$ edges with highest cost.

######  Lemma 4.5.

We have $c(M^{\texttt{ALG}}_{[2\gamma]})\leq c(M^{\texttt{OPT}})$.

###### Proof.

Let $M_{\setminus B}^{\texttt{ALG}}$ be the matching obtained from
$M^{\texttt{ALG}}$ by removing all edges incident to vertices in $B$. Since
$|B|\leq\gamma n$ we have $c(M^{\texttt{ALG}}_{[\gamma]})\leq c(M_{\setminus
B}^{\texttt{ALG}})$. Notice that all edges in $M_{\setminus B}^{\texttt{ALG}}$
are $1$-feasible. For each $(u,v)\in M_{\setminus B}^{\texttt{ALG}}$ we have
$c(u,v)=\varphi(u)+\varphi(v)$ and for each $(u,v)\in M^{\texttt{OPT}}$ we
have $\varphi(u)+\varphi(v)\leq c(u,v)+1$. Thus,

$c(M^{\texttt{ALG}}_{[\gamma]})\leq c(M_{\setminus
B}^{\texttt{ALG}})\leq\sum_{u\in V}\varphi(u)=\sum_{(u,v)\in
M^{\texttt{OPT}}}\varphi(u)+\varphi(v)\leq\sum_{(u,v)\in
M^{\texttt{OPT}}}c(u,v)+1=n+c(M^{\texttt{OPT}}).$

Now, it is sufficient to notice that, since all edges have costs in
$[1/\gamma,C/\gamma-1]$, removing any $\gamma n$ edges from
$M^{\texttt{ALG}}_{[\gamma]}$ decreases its cost by $n$. Thus,
$c(M^{\texttt{ALG}}_{[2\gamma]})\leq c(M^{\texttt{OPT}})$. ∎

Now, we are ready to prove Theorem 7.

###### Proof of Theorem 7.

Thanks to Lemma 4.5, we know that $c(M^{\texttt{ALG}}_{[2\gamma]})\leq
c(M^{\texttt{OPT}})$. Moreover, by Lemma 4.4 we have
$|M^{\texttt{ALG}}|=n-|F_{0}|\geq(1-4\gamma)n$, thus defining $M^{1-8\gamma}$
as the min-weight matching of size $(1-8\gamma)n$, we have
$c(M^{1-8\gamma})\leq c(M^{\texttt{ALG}}_{[4\gamma]})$. We are left to prove
that the estimate $\hat{c}=\frac{n}{|S|}\Sigma$ returned by Algorithm 1
satisfies $c(M^{\texttt{ALG}}_{[4\gamma]})\leq\hat{c}\leq
c(M^{\texttt{ALG}}_{[2\gamma]})$. Let $S$ and $\Sigma$ be defined as in
Algorithm 1 and let $w$ be maximum such that $3\gamma|S|$ edges in $S$ have
cost $\geq w$. If $\alpha_{w}\cdot n$ is the number of edges in
$M^{\texttt{ALG}}$ that cost $\geq w$, then using standard Chernoff Bounds
arguments we have that, whp, $|\alpha_{w}-3\gamma|\leq\gamma^{2}/C$. From now
on we condition on this event. Notice that
$\frac{(1-\alpha_{w})n}{(1-3\gamma)|S|}\Sigma$ is an unbiased estimator of
$c(M^{\texttt{ALG}}_{[\alpha_{w}]})$. Moreover, since all costs are in
$[1/\gamma,C/\gamma]$, then $O_{\gamma,C}(\log n)$ samples are sufficient to
have $\frac{(1-\alpha_{w})n}{(1-3\gamma)|S|}\Sigma$ concentrated, up to a
factor $(1\pm\frac{\gamma^{2}}{C})$, around
$c(M^{\texttt{ALG}}_{[\alpha_{w}]})$. Hence, assuming that $\gamma$ is
sufficiently small, we have

$\frac{n}{|S|}\Sigma\in(1\pm 3\gamma^{2}/C)\cdot
c(M^{\texttt{ALG}}_{[\alpha_{w}]})\subseteq
c(M^{\texttt{ALG}}_{[\alpha_{w}]})\pm 3\gamma n$

where the last containment relation holds because all costs are $\leq
C/\gamma$ and so $c(M^{\texttt{ALG}}_{[\alpha_{w}]})\leq Cn/\gamma$. Since all
costs are $\geq 1/\gamma$ we have
$c(M^{\texttt{ALG}}_{[\alpha_{w}+3\gamma^{2}]})\leq
c(M^{\texttt{ALG}}_{[\alpha_{w}]})-3\gamma n$ and
$c(M^{\texttt{ALG}}_{[\alpha_{w}-3\gamma^{2}]})\geq
c(M^{\texttt{ALG}}_{[\alpha_{w}]})+3\gamma n$. Thus, picking $\gamma$ small
enough to have $\alpha_{w}\pm 3\gamma^{2}\subseteq[2\gamma,4\gamma]$ we have

$c(M^{\texttt{ALG}}_{[4\gamma]})\leq\frac{n}{|S|}\Sigma\leq
c(M^{\texttt{ALG}}_{[2\gamma]}).$

Therefore, we have $c(M^{1-8\gamma})\leq\hat{c}\leq c(M^{\texttt{OPT}})$ and
rescaling $\gamma$ gives exactly the desired result. ∎

######  Observation 8.

As in the proof of Theorem 7, define $w$ as the maximum value such that there
are at least $3\gamma|S|$ edges with cost $\geq w$ in $S$ and define
$\alpha_{w}$ such that exactly $\alpha_{w}\cdot n$ edges in $M$ have cost
$\geq w$. We have, whp, $|\alpha_{w}-3\gamma|\leq\gamma^{2}/C$, thus for
$\gamma$ small enough $c(M^{\texttt{ALG}}_{[\alpha_{w}]})\leq
c(M^{\texttt{ALG}}_{[2\gamma]})\leq c(M^{\texttt{OPT}})$ and (up to rescaling
$\gamma$) $|M^{\texttt{ALG}}_{[\alpha_{w}]}|\geq(1-\gamma)n$. Moreover, given
an edge $e\in M^{\texttt{ALG}}$ we can decide whether $e\in
M^{\texttt{ALG}}_{[\alpha_{w}]}$ simply by checking $c(e)\leq w$.

##  5 Implementing the Template in Sublinear Time

In this section we explain how to implement _Step 1_ and _Step 2_ from the
template algorithm in sublinear time.

###  5.1 From Potential Oracles to Membership Oracles

Throughout this section, we would like to apply Theorem 5 and Theorem 6 on the
eligibility graph $G_{\mathcal{E}}=(V,E_{\mathcal{E}})$ and forward graph
$G_{F}=(V,E_{F})$. However, we do not have random access to the adjacency
matrix of these graphs. Indeed, to establish if $(u,v)\in V_{0}\times V_{1}$
is eligible we need to check the condition $\varphi(u)+\varphi(v)=c(u,v)+1$
(or $\varphi(u)+\varphi(v)=c(u,v)$). However, we will see that the potential
$\varphi(\cdot)$ requires more than a single query to be evaluated. Formally,
we assume that we have a potential oracle $\mathtt{eval}_{\varphi}(\cdot)$
that returns the value of $\varphi(\cdot)$ in time $t_{\varphi}$. Whenever
checking whether $(u,v)$ is an edge of $G_{F}$ ($G_{\mathcal{E}})$ requires to
evaluate a condition of the form $\varphi(u)+\varphi(v)=c(u,v)+1$ (or
$\varphi(u)+\varphi(v)=c(u,v)$) we say that we have _potential oracle access_
to the adjacency matrix of $G_{F}$ ($G_{\mathcal{E}}$) with potential oracle
time $t_{\varphi}$. We can think of $t_{\varphi}$ as
$\tilde{O}(n^{1+\varepsilon})$ and we will later prove that this is (roughly)
the case.

#### Potential functions with constant-size range.

If our potential function $\varphi:V\rightarrow\mathcal{R}$ has range size
$|\mathcal{R}|\leq R$ then we say that it is an $R$-potential. If the
eligibility (forward) graph is induced by $R$-potentials for $R=O(1)$ we can
rephrase Theorem 5 and Theorem 6 to work with potential oracle access, without
any asymptotic overhead. The following theorem is an analog of Theorem 5 for
forward graphs.

######  Lemma 5.1.

Let $G_{F}=(V,E_{F})$ be a forward graph w.r.t the $R$-potential $\varphi$,
let $A\subseteq V$ be a vertex set. Suppose we have a potential oracle
$\mathtt{eval}_{\varphi}$ with oracle time $t_{\varphi}$ and an membership
oracle $\mathtt{mem}_{A}$ with $t_{A}$ query time. We are given as input
constants $0<\varepsilon\leq 0.2$ and $\delta_{\mathrm{in}}>0$.

There exists an algorithm
$\texttt{LargeMatchingForward}(\varphi,A,\delta_{\mathrm{in}})$ that
preprocesses $G_{F}$ in $\tilde{O}_{R}((t_{A}+t_{\varphi}+n)\cdot
n^{1-\varepsilon})$ time and either returns $\bot$ or constructs a matching
oracle $\mathtt{match}_{M}(\cdot)$ for a matching $M\subset G_{F}[A]$ of size
at least $\delta_{\mathrm{out}}n$ where
$\delta_{\mathrm{out}}=\frac{1}{2000\cdot
R^{10}}\delta_{\mathrm{in}}^{5}=\Theta_{\delta_{\mathrm{in}},R}(1)$ that has
$\tilde{O}_{R}((t_{A}+t_{\varphi}+n)n^{4\varepsilon})$ worst-case query time.
If $\mu(G_{F}[A])\geq\delta_{\mathrm{in}}n$, then $\bot$ is not returned. The
guarantee holds with high probability.

###### Proof.

Without loss of generality, we assume that $\varphi$ takes values in $[R]$.
Suppose that $G_{F}[A]$ has a matching of size $\delta_{\mathrm{in}}n$. We
partition the edges $E_{F}[A]=E_{F}\cap(A\times A)$ into $R^{2}$ sets
$E_{0,0}\dots E_{R-1,R-1}$ such that $(u,v)\in E_{i,j}$ iff $\varphi(u)=i$ and
$\varphi(v)=j$. Then, there exist $i,j\in[R]$ such that $G_{i,j}=(V,E_{i,j})$
has a matching of size $\delta_{\mathrm{in}}n/R^{2}$. Moreover, once we
restrict ourselves to $G_{i,j}$, each edge query $(u,v)\in E_{i,j}$ becomes
much easier. Indeed, we just need to establish if $i+j=c(u,v)+1$. In order to
restrict ourselves to $G_{i,j}$ it suffices to set
$A^{\prime}=A\cap(\varphi^{-1}(\\{i\\})\times\varphi^{-1}(\\{j\\}))$. Then the
membership oracle $\mathtt{mem}_{A^{\prime}}$ runs in time
$O(t_{A}+t_{\varphi})$. Hence, using Theorem 5 we can find a matching of size
$\delta_{\mathrm{out}}n$, where $\delta_{\mathrm{out}}=\frac{1}{2000\cdot
R^{10}}\delta_{\mathrm{in}}^{5}$. Algorithmically, we run the algorithm from
Theorem 5 $R^{2}$ times (once for each pair $(i,j)$) and halt as soon as the
algorithm does not return $\bot$. ∎

The following is an analog of Theorem 6 for eligibility graphs.

######  Lemma 5.2.

Let $\varepsilon_{\texttt{in}}>0$ be a sufficiently small constant. Let
$\alpha_{k,\gamma}$ and $\beta_{k,\gamma}$ be constants that depend on $k$ and
$\gamma$ and set
$\varepsilon_{\texttt{out}}:=\alpha_{k,\gamma}\cdot\varepsilon_{\texttt{in}}$.
We have an $R$-potential oracle $\mathtt{eval}_{\varphi}$ with running time
$t_{\varphi}=\tilde{O}(n^{1+\varepsilon_{\texttt{in}}})$, a matching oracle
$\mathtt{match}_{M^{\texttt{in}}}$ with running time
$t_{M^{\texttt{in}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{in}}})$ and an
eligibility graph $G_{\mathcal{E}}=(V,E_{\mathcal{E}})$ w.r.t. $\varphi$ and
$M^{\texttt{in}}$.

There exists an algorithm
$\texttt{AugmentEligible}(\varphi,M^{\texttt{in}},k,\gamma,\varepsilon_{\texttt{in}})$
that runs in
$\tilde{O}_{k,\gamma,R}\left(n^{2-\varepsilon_{\texttt{in}}}\right)$ time.
Further, either it returns an oracle
$\mathtt{match}_{M^{\texttt{out}}}(\cdot)$ with query time
$\tilde{O}_{k,\gamma,R}(n^{1+\varepsilon_{\texttt{out}}})$, for some matching
$M^{\texttt{out}}$ in $G_{\mathcal{E}}$ of size
$|M^{\texttt{out}}|\geq|M^{\texttt{in}}|+\beta_{k,\gamma}\cdot n$ (we say that
it “succeeds” in this case), or it returns $\bot$. Finally, if the matching
$M^{\texttt{in}}$ admits a collection of $\gamma\cdot n$ many node-disjoint
augmenting paths with length $\leq k$ in $G_{\mathcal{E}}$, then the algorithm
succeeds whp.

###### Proof.

We derive Lemma 5.2 combining Theorem 6 and Lemma 5.1. First, we notice that
Theorem 6 says that the algorithm succeeds (whp) whenever there are
$\gamma^{\prime}n$ node-disjoint augmenting paths (NDAP) with length _exactly_
$2k^{\prime}+1$, while Lemma 5.2 has the weaker requirement that there are at
least $\gamma n$ NDAP of length $\leq k$. A simple reduction is obtained
invoking Theorem 6 with $\gamma^{\prime}=\gamma/k$ for all $k^{\prime}$ such
that $2k^{\prime}+1\leq k$ (notice that all augmenting paths have odd length).
In this way, if there exists a collection of $\gamma n$ NDAP of length $\leq
k$ then there exists a $k^{\prime}\leq(k-1)/2$ such that we have
$\gamma^{\prime}n$ NDAP of length _exactly_ $2k^{\prime}+1$. All guarantees
are preserved since we consider both $\gamma$ and $k$ constants. Now, we are
left to address the fact that we do not have random access to the adjacency
matrix of $G_{\mathcal{E}}$, but rather potential oracle access.

We notice that, according to Theorem 6, the implementation of Augment from
[BKS23] never makes any query to the adjacency matrix besides those performed
inside LargeMatching. Moreover, Lemma 5.1 implies that LargeMatchingForward is
not asymptotically slower than LargeMatching as long as $R=O(1)$. ∎

Finally, we observe that in Algorithm 1 each potential is increased (or
decreased) at most $T=O_{C,\gamma}(1)$ times. Hence, $\varphi$ is a
$R$-potential for $R=2T+1=O_{C,\gamma}(1)$. Thus, we can consider $R$ a
constant when applying Lemma 5.1 or Lemma 5.2.

###  5.2 Implementing Step 1

In this subsection we implement Step 1 from the template algorithm in
sublinear time. Here we assume that we have at our disposal a potential oracle
$\mathtt{eval}_{\varphi^{\texttt{in}}}$ running in time
$t_{\varphi^{\texttt{in}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{in}}})$ and a
matching oracle $\mathtt{match}_{M^{\texttt{in}}}$ with running time
$t_{M^{\texttt{in}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{in}}})$. We will
output a potential oracle $\mathtt{eval}_{\varphi^{\texttt{out}}}$ running in
time $t_{\varphi^{\texttt{out}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{out}}})$
and a matching oracle $\mathtt{match}_{M^{\texttt{out}}}$ with running time
$t_{M^{\texttt{out}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{out}}})$. We show
that there exists a $(k,\xi)$-QMSNDAP $\mathcal{A}$ such that: the matching
$M^{\texttt{out}}$ is obtained from $M^{\texttt{in}}$ by augmenting it along
all paths in $\mathcal{A}$; $\varphi^{\texttt{out}}$ is obtained from
$\varphi^{\texttt{in}}$ by subtracting $1$ to $\varphi^{\texttt{in}}(v)$ for
each $v\in V_{1}\cap\bigcup_{P\in\mathcal{A}}P$.

Set $k$ and $\gamma$ as in Algorithm 1.

Initialize $M\leftarrow M^{\texttt{in}}$ and
$\varepsilon\leftarrow\varepsilon_{\texttt{in}}$.

Repeat until AugmentEligible returns $\bot$:

  1. 1.

Let $\texttt{AugmentEligible}(G_{\mathcal{E}},M,k,\gamma,\varepsilon)$ return
$\mathtt{match}_{M^{\prime}}$ with running time
$t_{M^{\prime}}=\tilde{O}(n^{1+\varepsilon^{\prime}})$.

  2. 2.

Update $M\leftarrow M^{\prime}$ and
$\varepsilon\leftarrow\varepsilon^{\prime}$.

Set $M^{\texttt{out}}\leftarrow M$ and
$\varepsilon_{\texttt{out}}\leftarrow\varepsilon$.

Implement $\mathtt{eval}_{\varphi^{\texttt{out}}}(u)$ as follows:

  * •

If $u\in V_{0}$, return $\mathtt{eval}_{\varphi^{\texttt{in}}}$.

  * •

Else, $u\in V_{1}$, set $v\leftarrow\mathtt{match}_{M^{\texttt{out}}}(u)$.

  * •

If $v\texttt{ == }\bot$, return $\mathtt{eval}_{\varphi^{\texttt{in}}}(u)$.

  * •

Else, we have $(u,v)\in M^{\texttt{out}}$:

    * –

If $c(u,v)+1\texttt{ ==
}\mathtt{eval}_{\varphi^{\texttt{in}}}(u)+\mathtt{eval}_{\varphi^{\texttt{in}}}(v)$,
return $\mathtt{eval}_{\varphi^{\texttt{in}}}(u)-1$.

    * –

Else, return $\mathtt{eval}_{\varphi^{\texttt{in}}}(u)$.

Algorithm 2 Implementation of Step 1.

#### Analysis.

First, we observe that the algorithm above correctly implements the template,
with high probability (all our statements henceforth hold whp). Initialize
$\mathcal{A}\leftarrow\emptyset$. For each run of
$\texttt{AugmentEligible}(G,M,k,\gamma,\varepsilon)$ we decompose $M\oplus
M^{\prime}$ into a set of augmenting paths $\mathcal{P}$ and a set of
alternating cycles $\mathcal{C}$ and we set
$\mathcal{A}\leftarrow\mathcal{A}\cup\mathcal{P}$. When
$\texttt{AugmentEligible}(G,M,k,\gamma,\varepsilon)$ returns $\bot$ it means
(by Lemma 5.2) that there are at most $\gamma n$ node-disjoint augmenting
paths of length $\leq k$ that do not intersect $\bigcup\mathcal{A}$. Hence,
$\mathcal{A}$ is a $(k,\xi)$-QMSNDAP . Clearly,
$\mathtt{match}_{M^{\texttt{out}}}$ implements the matching obtained from
$M^{\texttt{in}}$ by augmenting along the paths in $\mathcal{A}$.

To see that the implementation of $\mathtt{eval}_{\varphi^{\texttt{out}}}(u)$
is correct it is sufficient to notice that in the template algorithm we
decrement $\varphi(u)$ iff: $(i)$ $u\in V_{1}$, and $(ii)$ there exists an
augmenting path $P\in\mathcal{A}$ intersecting $u$. Since every node belongs
to at most one path in $\mathcal{A}$ then $u$ is matched in $M^{\texttt{out}}$
and $(u,v)\in M^{\texttt{out}}$ is an $M^{\texttt{in}}$-eligible edge. Thus,
$(ii)$ is equivalent to: $(iii)$ $v=\mathtt{match}_{M^{\texttt{out}}}$
satisfies $\varphi^{\texttt{in}}(v)+\varphi^{\texttt{in}}(u)=c(u,v)+1$.
Finally, we bound $\varepsilon_{\texttt{out}}$ as a function of
$\varepsilon_{\texttt{in}}$.

######  Lemma 5.3.

Step 1 can be implemented in $\tilde{O}(n^{2-\varepsilon})$ time for some
constant $\varepsilon>0$. Moreover, the oracle
$\mathtt{match}_{M^{\texttt{out}}}$ has running time $t_{M^{\texttt{out}}}$
and the oracle $\mathtt{eval}_{\varphi^{\texttt{out}}}$ has running time
$t_{\varphi^{\texttt{out}}}$ such that
$t_{M^{\texttt{out}}},t_{\varphi^{\texttt{out}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{out}}})$
and $\varepsilon_{\texttt{out}}=O_{\gamma,k}(\varepsilon_{\texttt{in}})$.

###### Proof.

Let $\varepsilon>0$ and $\beta_{k,\gamma}$ as in Lemma 5.2. Algorithm 2 runs
AugmentEligible at most $1/\beta_{k,\gamma}+1=O_{k,\gamma}(1)$ times because
the set $\mathcal{A}$ increases by $\beta_{k,\gamma}\cdot n$ after each
successful run of AugmentEligible. Thus, there can be at most
$1/\beta_{k,\gamma}$ successful runs. It is apparent that, by Lemma 5.2, Step
1 can be implemented in $\tilde{O}_{k,\gamma}(n^{2-\varepsilon})$ time.

Now we prove the bound on oracles time. First, we observe that
$t_{\varphi^{\texttt{out}}}=O(t_{M^{\texttt{out}}}+t_{\varphi^{\texttt{in}}})=\tilde{O}(n^{1+\varepsilon_{\texttt{out}}})$.
Moreover, at every iteration we have
$\varepsilon^{\prime}\leq\alpha_{k,\gamma}\cdot\varepsilon$, hence
$\varepsilon_{\texttt{out}}\leq\alpha_{k,\gamma}^{1/\beta_{k,\gamma}+1}\varepsilon_{\texttt{in}}=O_{k,\gamma}(\varepsilon_{\texttt{in}})$.
∎

###  5.3 Implementing Step 2

In this subsection we implement Step 2 from Algorithm 1 in sublinear time.
Once again, we assume that we have at our disposal a potential oracle
$\mathtt{eval}_{\varphi^{\texttt{in}}}$ running in time
$t_{\varphi^{\texttt{in}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{in}}})$ and a
matching oracle $\mathtt{match}_{M^{\texttt{in}}}$ with running time
$t_{M^{\texttt{in}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{in}}})$. We will
output a potential oracle $\mathtt{eval}_{\varphi^{\texttt{out}}}$ running in
time $t_{\varphi^{\texttt{out}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{out}}})$.
We show that there exists a $(k,\delta)$-QMF$\mathcal{F}$ with respect to
$M^{\texttt{in}}$ such that
$\varphi^{\texttt{out}}(u)=\varphi^{\texttt{in}}(u)+1$ for each
$u\in\mathcal{F}\cap V_{0}$ and
$\varphi^{\texttt{out}}(v)=\varphi^{\texttt{in}}(v)-1$ for each
$v\in\mathcal{F}\cap V_{1}$.

The execution of Algorithm 3 is represented in Figure 1, where vertices
colored in the same way are added to $\mathcal{F}$ during the same iteration.

Set $\delta$ as in Algorithm 1.

Initialize $t\leftarrow 0$, $\mathcal{F}_{0}\leftarrow F_{0}$, where $F_{0}$
is the set of $M^{\texttt{in}}$-unmatched vertices in $V_{0}$.

Implement $\mathtt{mem}_{\mathcal{F}_{0}}(u)$ as:
$\mathtt{match}_{M^{\texttt{in}}}(u)\texttt{ == }\bot$.

Repeat until LargeMatchingForward returns $\bot$:

  1. 1.

$A_{t}\leftarrow(\mathcal{F}_{t}\cap
V_{0})\cup(V_{1}\setminus\mathcal{F}_{t})$.

  2. 2.

Let $\texttt{LargeMatchingForward}(\varphi,A_{t},\delta)$ return
$\mathtt{match}_{M_{t}}$.

  3. 3.

$\mathcal{F}^{\prime}_{t}\leftarrow\mathcal{F}_{t}\cup\\{\mathtt{match}_{M_{t}(u)}\;|\;u\in\mathcal{F}_{t}\\}$

Implement $\mathtt{mem}_{\mathcal{F}^{\prime}_{t}}(u)$ as:
$\mathtt{mem}_{\mathcal{F}_{t}}(u)$ or
$\mathtt{match}_{M_{t}}(u)\in\mathcal{F}_{t}$.

  4. 4.

$\mathcal{F}^{\prime\prime}_{t}\leftarrow\mathcal{F}_{t}^{\prime}\cup\\{\mathtt{match}_{M^{\texttt{in}}}(u)\;|\;u\in\mathcal{F}^{\prime}_{t}\\}$

Implement $\mathtt{mem}_{F^{\prime\prime}_{t}}(u)$ as:
$\mathtt{mem}_{\mathcal{F}^{\prime}_{t}}(u)$ or
$\mathtt{match}_{M^{\texttt{in}}}(u)\in\mathcal{F}^{\prime}_{t}$.

  5. 5.

$\mathcal{F}_{t+1}\leftarrow\mathcal{F}^{\prime\prime}_{t}$; $t\leftarrow
t+1$.

Implement $\mathtt{eval}_{\varphi^{\texttt{out}}}(u)$ as
$\mathtt{eval}_{\varphi^{\texttt{in}}}(u)+\mathtt{mem}_{\mathcal{F}_{t}}(u)\cdot(-1)^{\mathbbm{1}_{u\in
V_{1}}}$

Algorithm 3 Implementation of Step 2.

#### Analysis.

First, we prove that Algorithm 3 implements the template (all guarantees hold
whp). Namely, that $\mathcal{F}$ is a $(k,\delta)$-QMF, where $k$ and $\delta$
are defined as in Algorithm 1. With a slight abuse of notation, in Algorithm 3
we used $\mathcal{F}$ to denote the set of nodes in the forest. Here, we
understand that for each
$u\in\mathcal{F}^{\prime}_{t}\setminus\mathcal{F}_{t}$ we have an edge
$(u,\mathtt{match}_{M_{t+1}}(u))$ and for each
$v\in\mathcal{F}^{\prime\prime}_{t}\setminus\mathcal{F}^{\prime}_{t}$ we have
an edge $(v,\mathtt{match}_{M^{\texttt{in}}}(v))$. Let $\tau$ be the total
number of times LargeMatchingForward runs successfully in Algorithm 3. We will
see that $\tau\leq k/2$. Notice that $\mathcal{F}_{\tau}$ is the last forest
produced by Algorithm 3 and for each $u\in\mathcal{F}_{\tau}\setminus F_{0}$
we add an edge incident to $u$, thus $\mathcal{F}_{\tau}$ is a forest with
$|F_{0}|$ connected components, one for each $u\in F_{0}$. Now we show that
$\mathcal{F}_{\tau}$ is a $(k,\delta)$-QMFw.r.t. $M^{\texttt{in}}$. We refer
to the notation of Definition 3.6. Item 1 is clearly satisfied. Item 2 is
satisfied because of line 4 in Algorithm 3.

Now we show that Item 3 is satisfied. Define $k=6000(2T+1)^{10}/\delta^{5}$ as
in Algorithm 1 and recall that $\varphi$ is a $(2T+1)$-potential. Thanks to
Lemma 5.1, at each step we increment $|\mathcal{F}|$ by at least
$\frac{1}{2000(2T+1)^{10}}\cdot\delta^{5}n$. Thus, no more than $\lceil
2000(2T+1)^{10}/\delta^{5}\rceil\leq k/2$ iterations are performed and we
cannot have more than $k$ hops between $u\in\mathcal{F}$ and $v\in F_{0}$ if
$u$ belongs to the connected component of $v$.

Now we prove that Item 4 is satisfied. At each iteration, the size of each
connected component of $\mathcal{F}_{t}$ at most triples. Indeed, let $C$ be a
connected component of $\mathcal{F}$. In step 3 we add to $C$ at most $|C|$
vertices (because we add a vertex for each edge in a matching incident to $C$)
and in step 4 we add to $C$ at most one more vertex for each new vertex added
in step 3.

Now we prove that Item 5 is satisfied. Algorithm 3 halts when
$\texttt{LargeMatchingForward}(M^{\texttt{in}},(\mathcal{F}\cap
V_{0})\cup(V_{1}\setminus\mathcal{F}),\delta)$ returns $\bot$. This may only
happen when there is no matching between of $\mathcal{F}\cap V_{0}$ and
$V_{1}\setminus\mathcal{F}$ of size $\delta n$. This implies that there exists
a vertex cover of size $\leq\delta n$. Moreover, this is a vertex cover for
the whole $E_{\mathcal{E}}\cap(\mathcal{F}\times V\setminus\mathcal{F})$
because all edges in $E_{\mathcal{E}}\cap V_{1}\times V_{0}$ are in
$M^{\texttt{in}}$ and by Item 2 have both endpoints either in $\mathcal{F}$ or
in $V\setminus\mathcal{F}$.

It is easy to check that
$\varphi^{\texttt{out}}(u)=\varphi^{\texttt{in}}(u)+1$ for each
$u\in\mathcal{F}\cap V_{0}$ and
$\varphi^{\texttt{out}}(v)=\varphi^{\texttt{in}}(v)-1$ for each
$v\in\mathcal{F}\cap V_{1}$.

######  Lemma 5.4.

Step 2 can be implemented in $\tilde{O}(n^{2-\varepsilon})$ time for some
constant $\varepsilon>0$. Moreover, the oracle
$\mathtt{eval}_{\varphi_{\texttt{out}}}$ has running time
$t_{\varphi^{\texttt{out}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{out}}})$ and
$\varepsilon_{\texttt{out}}=O_{k,\delta}(\varepsilon_{\texttt{in}})$.

###### Proof.

For $s=0\dots\tau$ denote with $\varepsilon_{s}>0$ a constant such that
$t_{A_{s}}=\tilde{O}(n^{1+\varepsilon_{s}})$, where $t_{A_{s}}$ is the running
time of $\mathtt{mem}_{A_{s}}$. Notice that
$\varepsilon_{0}=\varepsilon_{\texttt{in}}$. At step $s$ we choose
$\hat{\varepsilon}_{s}:=2\varepsilon_{s}$ as the $\varepsilon$ parameter in
Lemma 5.1. This implies that LargeMatchingForward runs in
$\tilde{O}(n^{1+\varepsilon_{s}}\cdot
n^{1-\hat{\varepsilon}_{s}})=\tilde{O}(n^{2-\varepsilon_{s}})$ time. We have
already proved that $\tau\leq k$, thus Algorithm 2 takes
$\tilde{O}(n^{2-\varepsilon})$ time in total, where
$\varepsilon:=\min_{s\in[0,\tau]}\varepsilon_{s}=\varepsilon_{\texttt{in}}$.

Denote with $t_{\mathcal{F}}$ the query time of $\mathtt{mem}_{\mathcal{F}}$.
For each $s$, we have
$t_{\mathcal{F}_{s+1}}=t_{M_{s+1}}+t_{M^{\texttt{in}}}+t_{\mathcal{F}_{s}}$.
Thanks to Lemma 5.1 we have
$t_{M_{s+1}}=\tilde{O}((t_{A_{s}}+t_{\varphi^{\texttt{in}}}+n)n^{4\hat{\varepsilon}_{s}})$.
Moreover, $t_{A_{s}}=t_{\mathcal{F}_{s}}$. Thus,
$t_{\mathcal{F}_{s+1}}=(t_{\mathcal{F}_{s}}+t_{\varphi^{\texttt{in}}}+n)n^{8\varepsilon_{s}}+t_{M^{\texttt{in}}}+t_{\mathcal{F}_{s}}$.
Since,
$t_{\mathcal{F}_{0}}=t_{\varphi^{\texttt{in}}}=t_{M^{\texttt{in}}}=\tilde{O}(n^{1+\varepsilon_{\texttt{in}}})$
we have
$t_{\varphi^{\texttt{out}}}=t_{\varphi^{\texttt{in}}}+t_{\mathcal{F}_{\tau}}=\tilde{O}(n^{1+9^{\tau}\cdot\varepsilon_{\texttt{in}}})=\tilde{O}_{k}(n^{1+O_{k,\delta}(\varepsilon_{\texttt{in}})})$.
∎

###  5.4 Implementing the Template Algorithm

We can put together the results proved in the previous subsections and show
that Algorithm 1 can be implemented in sublinear time.

######  Theorem 9.

There exists a constant $\varepsilon>0$ such that Algorithm 1 can be
implemented in time $O(n^{2-\varepsilon})$. Moreover, using the notation in 8,
we can return a matching oracle
$\mathtt{match}_{M^{\texttt{ALG}}_{[\alpha_{w}]}}$ running in time
$O(n^{1-\varepsilon})$ such that $M^{\texttt{ALG}}_{[\alpha_{w}]}$ satisfies
$|M^{\texttt{ALG}}_{[\alpha_{w}]}|\geq(1-\gamma)n$ and
$c(M^{\texttt{ALG}}_{[\alpha_{w}]})\leq c(M^{\texttt{OPT}})$ and
$\mathtt{match}_{M^{\texttt{ALG}}_{[\alpha_{w}]}}$.

###### Proof.

Algorithm 1 runs $T=O_{C,\gamma}(1)$ iterations, and a single iterations
consists of Step 1 and Step 2. At iteration $s$ denote with
$\varepsilon^{(s)}_{\texttt{in}}$ the value of $\varepsilon_{\texttt{in}}$ for
Step 1 input (or, equivalently, the value of $\varepsilon_{\texttt{out}}$ for
Step 2 output at iteration $s-1$) and with $\varepsilon^{(s)}_{\texttt{out}}$
the value of $\varepsilon_{\texttt{out}}$ for Step 1 output (or, equivalently,
the value of $\varepsilon_{\texttt{in}}$ for Step 2 input at iteration $s$).
Every time we run either Step 1 or Step 2, the value of
$\varepsilon_{\texttt{out}}$ is at most some constant factor larger than
$\varepsilon_{\texttt{in}}$. This translates into
$\varepsilon^{(s)}_{\texttt{in}}=O_{C,k,\gamma}(\varepsilon^{(s-1)}_{\texttt{out}})$
and
$\varepsilon^{(s)}_{\texttt{out}}=O_{C,k,\gamma}(\varepsilon^{(s)}_{\texttt{in}})$.
Thus, after $T$ iterations $\varepsilon^{(T)}_{\texttt{out}}$ is arbitrarily
small, provided that $\varepsilon^{(0)}_{\texttt{in}}$ is small enough. To
conclude, we notice that the initial matching is empty and the initial
potential is identically $0$, so the first membership oracle and potential
oracle run in linear linear, thus we can set $\varepsilon^{(0)}_{\texttt{in}}$
arbitrarily small. Finally, let $M^{\texttt{ALG}}$ be the last matching
computed by Algorithm 1. We have at our disposal a matching oracle
$\mathtt{match}_{M^{\texttt{ALG}}}$ running in time
$\tilde{O}(n^{1+\varepsilon_{\texttt{in}}^{(T+1)}})$, so we can easily sample
the a $S$ of $O(\log n)$ edges from $M^{\texttt{ALG}}$ in time
$\tilde{O}(n^{1+\varepsilon_{\texttt{out}}^{(T)}})$. This conclude the
implementation of Algorithm 1.

Moreover, we compute $w$ as the largest value such that at least $3\gamma|S|$
edges in $S$ have cost $\geq w$ and define $\alpha_{w}$ such that exactly
$\alpha_{w}\cdot n$ edges in $M^{\texttt{ALG}}$ have cost $\geq w$. Then, we
implement a matching oracle $\mathtt{match}_{M^{\texttt{ALG}}_{[\alpha_{w}]}}$
for $M^{\texttt{ALG}}_{[\alpha_{w}]}$ running in time
$\tilde{O}(n^{1+\varepsilon_{\texttt{out}}^{(T)}})$ as follows: given $u\in
V_{0}\cup V_{1}$ we set $v\leftarrow\mathtt{match}_{M^{\texttt{ALG}}}(u)$; if
$c(u,v)<w$ then we return $v$, else we return $\bot$. Thanks to 8, we have
$|M^{\texttt{ALG}}_{[\alpha_{w}]}|\geq(1-\gamma)n$ and
$c(M^{\texttt{ALG}}_{[\alpha_{w}]})\leq c(M^{\texttt{OPT}})$. ∎

##  6 Proof of our Main Theorems

In this section we piece things together and prove Theorem 3. Then, we use
Theorem 3 to prove Theorem 1, Corollary 1.1 and Theorem 2.

###  6.1 Proof of Theorem 3

In this subsection we strengthen Theorem 7, extend its scope to arbitrary
costs and combine it with Theorem 9 to obtain Theorem 3. We restate the latter
for convenience.

See 3

#### Roadmap of the proof.

Theorem 7 works only for weights in $[1,C]$. In order to reduce to that case,
we need to find a _characteristic cost_ $\bar{w}$ of min-weight matchings with
size in $[\alpha n,\beta n]$. Then, we round every cost to a multiple of
$\frac{1}{2}\gamma^{2}\bar{w}$, where $\gamma$ is a small constant. We show
that, thanks to certain properties of the characteristic cost $\bar{w}$, the
approximation error induced by rounding the costs is negligible. Finally, we
pad each size of the bipartition with dummy vertices to reduce the problem of
finding a matching of approximate size $\beta n$ to that of finding an
_approximate perfect matching_ , which is addressed in Theorem 7.

#### Notation.

Similarly to Theorem 3, we denote with $M^{\xi}$ the min-weight matching of
size $\xi n$ in $G$. Likewise, we will define a graph $\widebar{G}$ and denote
with $\widebar{M}^{\xi}$ the min-weight matching of size $\xi n$ in
$\widebar{G}$. As in Section 5, given a matching $M$, we denote with
$M_{[\delta]}$ the matching obtained from $M$ by removing the $\delta n$ most
expensive edges. We denote with $\mu(M)$ the cost of the most expensive edge
in $M$. Given $w\geq 0$, we denote with $G_{\leq w}$ the graph of edges which
cost $\leq w$. Throughout this subsection, fix a constant
$0<\gamma<(\beta-\alpha)/4$.

#### Reduction from arbitrary weights to $[1,C]$.

The next technical lemma shows that, if we can can solve an easier version of
the problem in Theorem 3 where we allow an additive error $\gamma^{2}\bar{w}n$
on an instance where $\bar{w}$ is an upper bound for the cost function; then
we can also solve the problem in Theorem 3. This reduction is achieved by
finding a suitable characteristic cost $\bar{w}$ in sublinear time and running
the aforementioned algorithm on $G_{\leq\bar{w}}$.

######  Lemma 6.1.

Suppose that there exists an algorithm that takes as input a bipartite graph
$\widebar{G}=(\widebar{V}_{0}\cup\widebar{V}_{1},\widebar{E})$ endowed with a
cost function $\bar{c}:\widebar{E}\rightarrow[0,\bar{w}]$, outputs an estimate
$\hat{c}$ and a matching oracle $\mathtt{match}_{\hat{M}}$ such that (whp)
$\hat{c}$ satisfies

$\displaystyle\bar{c}(\widebar{M}^{\alpha})\leq\hat{c}\leq\bar{c}(\widebar{M}^{\alpha+\gamma})+\gamma^{2}\bar{w}n$

while $\hat{M}$ satisfies $|\hat{M}|\geq\alpha n$ and
$c(\hat{M})\leq\bar{c}(\widebar{M}^{\alpha+\gamma})+\gamma^{2}\bar{w}n$.
Suppose also that such algorithm runs in time $O(\bar{n}^{2-\varepsilon})$ and
$\mathtt{match}_{\hat{M}}$ runs in time $O(\bar{n}^{1+\varepsilon})$ for some
$\varepsilon>0$, where $\bar{n}=|\widebar{V}_{0}|=|\widebar{V}_{1}|$.

Then, there exists an algorithm that takes as input a bipartite graph
$G=(V_{0}\cup V_{1},E)$ endowed with a cost function
$c:E\rightarrow\mathbb{R}^{+}$, outputs an estimate $\hat{c}$ and a matching
oracle $\mathtt{match}_{\hat{M}}$ such that (whp) $\hat{c}$ satisfies

$C(M^{\alpha})\leq\hat{c}\leq c(M^{\beta})$

while $\hat{M}$ satisfies $|\hat{M}|\geq\alpha n$ and $c(\hat{M})\leq
c(M^{\beta})$. Moreover, such algorithm runs in time $O(n^{2-\varepsilon})$
and $\mathtt{match}_{\hat{M}}$ runs in time $O(n^{1+\varepsilon})$ for some
$\varepsilon>0$, where $n=|V_{0}|=|V_{1}|$.

###### Proof.

First, we show how to compute, in time $O(n^{2-\varepsilon})$, a value
$\bar{w}$ such that:

  1. (i)

$\gamma\cdot\bar{w}\leq\mu(M^{\beta}_{[\gamma]})$

  2. (ii)

$\bar{w}\geq\mu(M^{\alpha+3\gamma}_{[2\gamma]})$.

We sample $s=\Theta(n\log n/\gamma)$ edges from $G$ uniformly at random. Let
$w_{1}\leq w_{2}\leq\dots\leq w_{s}$ be their costs. Recall that Theorem 4
allows us to compute the size of a maximal-cardinality matching (MCM) of the
graph $G$, up to a $\gamma n$-additive approximation, in time
$O(n^{2-\Omega_{\gamma}(1)})$. Denote that algorithm with
$\texttt{ApproximateMatching}(G,\gamma)$. Using binary search, we find the
largest cost $w_{i}$ such that $\texttt{ApproximateMatching}(G_{\leq\gamma
w_{i}},\gamma)$ returns an estimated MCM size $<(\beta-2\gamma)n$. Then, we
set $\bar{w}:=w_{i}$.

We prove that property $(i)$ holds. Suppose that
$\mu(M^{\beta}_{[\gamma]})<\gamma w_{i}$. Then, in $G_{\leq\gamma w_{i}}$
there exists a matching of size $(\beta-\gamma)n$, therefore
$\texttt{ApproximateMatching}(G_{\leq\gamma w_{i}},\gamma)$ finds a matching
of size $\geq(\beta-2\gamma)n$ whp, contradiction.

We prove that property $(ii)$ holds. First, we prove that
$w_{i+1}\geq\mu(M^{\alpha+3\gamma}_{[\gamma]})$. Indeed, suppose the reverse
(strict) inequality holds. Then, for each matching $M$ of size
$(\beta-2\gamma)n$ we have

$c(M)\geq c(M^{\beta-2\gamma})\geq c(M^{\alpha+3\gamma})>\gamma\cdot w_{i+1}n$

which implies that there exists $e\in M$ such that $c(e)>\gamma\cdot w_{i+1}$.
However, this cannot hold for each matching $M$ of size $(\beta-2\gamma)n$
because $\texttt{ApproximateMatching}(G_{\leq\gamma w_{i+1}},\gamma)$ returned
(whp) a matching (oracle) of size $\geq(\beta-2\gamma)n$. Contradiction.
Therefore, we have $w_{i+1}\geq\mu(M^{\alpha+3\gamma}_{[\gamma]})$. However,
since we sampled $\Theta(n\log n/\gamma)$ edges, then for each $i$ there are,
whp, at most $\gamma\cdot n$ edges which cost $w$ satisfies $w_{i}<w<w_{i+1}$.
Hence, removing $\gamma n$ more edges from $M^{\alpha+3\gamma}_{[\gamma]}$ we
obtain $w_{i}\geq\mu(M^{\alpha+3\gamma}_{[2\gamma]})$.

We define $\widebar{G}:=G_{\leq\bar{w}}$ and $\bar{c}=c|_{\widebar{E}}$, run
the algorithm in the premise of the lemma on $\widebar{G}$ and $\bar{c}$ and
let $\hat{c}$, $\mathtt{match}_{\hat{M}}$ be its outputs. It is apparent that
this reduction takes $O(n^{2-\varepsilon})$ for some $\varepsilon>0$.

Since $\widebar{G}$ is a subgraph of $G$, we have $c(M^{\alpha})\leq
c(\widebar{M}^{\alpha})$. Moreover, conditions $(i)$ and $(ii)$, together with
$5\gamma\leq\beta-\alpha$ imply

$c(\widebar{M}^{\alpha+\gamma})\leq c(M^{\alpha+3\gamma}_{[2\gamma]})\leq
c(M^{\alpha+3\gamma})\leq c(M^{\beta-\gamma})\leq c(M^{\beta}_{[\gamma]})\leq
c(M^{\beta})-\gamma n\cdot\mu(M^{\beta}_{[\gamma]})\leq
c(M^{\beta})-\gamma^{2}\bar{w}n.$

Thus, $c(\widebar{M}^{\alpha})\leq\hat{c}\leq
c(\widebar{M}^{\alpha+\gamma})+\gamma^{2}\bar{w}n$ implies
$c(M^{\alpha})\leq\hat{c}\leq c(M^{\beta})$ and $c(\hat{M})\leq
c(\widebar{M}^{\alpha+\gamma})+\gamma^{2}\bar{w}n$ implies $\hat{c}\leq
c(M^{\beta})$. ∎

The following lemma shows how to reduce from real-values costs in $[0,w]$
(where possibly $w=\omega(1)$) to the more tame case where costs are integers
in $[1,C]$. This reduction is achieved via rounding.

######  Lemma 6.2.

Suppose that there exists an algorithm that takes as input a bipartite graph
$\widebar{G}=(\widebar{V}_{0}\cup\widebar{V}_{1},\widebar{E})$ endowed a cost
function $\bar{c}:E\rightarrow[1,C]$, with $C=O(1)$, returns an estimate
$\hat{c}$ and a matching oracle $\mathtt{match}_{\hat{M}}$ such that (whp)
$\hat{c}$ satisfies

$\bar{c}(\widebar{M}^{\alpha})\leq\hat{c}\leq\bar{c}(\widebar{M}^{\beta})$

while $\hat{M}$ satisfies $|\hat{M}|\geq\alpha n$ and
$\bar{c}(\hat{M})\leq\bar{c}(\widebar{M}^{\beta})$. Suppose also that such
algorithm runs in time $O(\bar{n}^{2-\varepsilon})$ and
$\mathtt{match}_{\hat{M}}$ runs in time $O(\bar{n}^{1+\varepsilon})$ for some
$\varepsilon>0$, where $\bar{n}=|\widebar{V}_{0}|=|\widebar{V}_{1}|$.

Then, there exists an algorithm that takes as input a bipartite graph
$G=(V_{0}\cup V_{1},E)$ endowed a cost function $c:E\rightarrow[0,w]$
(possibly $w=\omega(1)$), returns an estimate $\tilde{c}$ and a matching
oracle $\mathtt{match}_{\tilde{M}}$ such that (whp) $\tilde{c}$ satisfies

$c(M^{\alpha})\leq\tilde{c}\leq c(M^{\beta})+\gamma^{2}wn$

while $\tilde{M}$ satisfies $|\tilde{M}|\geq\alpha n$ and $c(\tilde{M})\leq
c(M^{\beta})+\gamma^{2}wn$. Moreover, such algorithm runs in time
$O(n^{2-\varepsilon})$ and $\mathtt{match}_{\hat{M}}$ runs in time
$O(n^{1+\varepsilon})$ for some $\varepsilon>0$, where $n=|V_{0}|=|V_{1}|$.

###### Proof.

We define $\bar{c}(e)=\left\lceil\frac{2c(e)}{\gamma^{2}w}\right\rceil+1$.
Then, the maximum value of $\bar{c}$ on $\widebar{G}$ is
$C:=2/\gamma^{2}+2=O(1)$. We set $\widebar{G}=G$ and run the algorithm in the
premise of the lemma on $\widebar{G}$ and $\bar{c}$. Let $\hat{c}$,
$\mathtt{match}_{\hat{M}}$ be its outputs. We define
$\tilde{c}:=\frac{1}{2}\gamma^{2}w\cdot\hat{c}$ and $\tilde{M}:=\hat{M}$. The
definition of $\bar{c}$ implies that, for each edge $e$ in $\widebar{G}$,
$c(e)\leq\frac{1}{2}\gamma^{2}w\cdot\bar{c}(e)\leq c(e)+\gamma^{2}w$. Hence,

$\frac{1}{2}\gamma^{2}w\cdot\bar{c}(\widebar{M}^{\alpha})\geq
c(\widebar{M}^{\alpha})\geq c(M^{\alpha})$

and

$\frac{1}{2}\gamma^{2}w\cdot\bar{c}(\widebar{M}^{\beta})\leq\frac{1}{2}\gamma^{2}w\cdot\bar{c}(M^{\beta})\leq
c(M^{\beta})+\gamma^{2}wn.$

Therefore,
$\bar{c}(\widebar{M}^{\alpha})\leq\hat{c}\leq\bar{c}(\widebar{M}^{\beta})$
implies $c(M^{\alpha})\leq\tilde{c}\leq c(M^{\beta})+\gamma^{2}wn$ and
$\bar{c}(\hat{M})\leq\bar{c}(\widebar{M}^{\beta})$ implies
$c(\hat{M})\leq\frac{1}{2}\gamma^{2}w\cdot\bar{c}(\hat{M})\leq\frac{1}{2}\gamma^{2}w\cdot\bar{c}(\widebar{M}^{\beta})\leq
c(M^{\beta})+\gamma^{2}wn$. ∎

#### Reduction from size-$\beta n$ matching to perfect matching.

The following lemma shows that, if we can approximate the min-weight of a
perfect matching (allowing $\delta n$ outliers), then we can approximate the
min-weight of a size-$\beta n$ matching (allowing $(\beta-\alpha)n$ outliers).
This reduction is achieved by padding the original graph with dummy vertices.

######  Lemma 6.3.

Suppose that, for each $\delta>0$, there exists an algorithm that takes as
input a bipartite graph
$\widebar{G}=(\widebar{V}_{0}\cup\widebar{V}_{1},\widebar{E})$ endowed a cost
function $\bar{c}:E\rightarrow[1,C]$, with $C=O(1)$, returns an estimate
$\hat{c}$ and a matching oracle $\mathtt{match}_{\hat{M}}$ such that (whp)
$\hat{c}$ satisfies

$\bar{c}(\widebar{M}^{1-\delta})\leq\hat{c}\leq\bar{c}(\widebar{M}^{1})$

while $\hat{M}$ satisfies $|\hat{M}|\geq(1-\delta)n$ and
$c(\hat{M})\leq\bar{c}(\widebar{M}^{1})$. Suppose also that such algorithm
runs in time $O(\bar{n}^{2-\varepsilon})$ and $\mathtt{match}_{\hat{M}}$ runs
in time $O(\bar{n}^{1+\varepsilon})$ for some $\varepsilon>0$, where
$\bar{n}=|\widebar{V}_{0}|=|\widebar{V}_{1}|$.

Then, for each $0\leq\alpha<\beta\leq 1$ there exists an algorithm that takes
as input a bipartite graph $G=(V_{0}\cup V_{1},E)$ and $c:E\rightarrow[1,C]$,
returns an estimate $\tilde{c}$ and a matching oracle
$\mathtt{match}_{\tilde{M}}$ such that (whp) $\tilde{c}$ satisfies

$c(M^{\alpha})\leq\tilde{c}\leq c(M^{\beta})$

while $\tilde{M}$ satisfies $|\tilde{M}|\geq\alpha n$ and $c(\tilde{M})\leq
c(M^{\beta})$. Moreover, such algorithm runs in time $O(n^{2-\varepsilon})$
and $\mathtt{match}_{\tilde{M}}$ runs in time $O(n^{1+\varepsilon})$ for some
$\varepsilon>0$, where $n=|V_{0}|=|V_{1}|$.

###### Proof.

Fix a constant $0<\xi\leq(\alpha-\beta)/2$. We construct $\widebar{G}$,
starting from $\widebar{G}=G$ and $\bar{c}=c$, as follows. We add a set of
$(1-\beta+\xi)n$ dummy vertices on each side of the bipartition:
$\widebar{V}_{0}=V_{0}\cup D_{0}$ and $\widebar{V}_{1}=V_{1}\cup D_{1}$. Add
an edge $(d_{0},v_{1})$ to $E$ for each $(d_{0},v_{1})\in D_{0}\times V_{1}$
and set $\bar{c}(d_{0},v_{1})=1$. Do the same for each $(v_{0},d_{1})\in
V_{0}\times D_{1}$. Notice that we construct both the adjacency matrix and the
cost function implicitly, because an explicit construction would take
$\Omega(n^{2})$ time. We have
$\bar{n}:=|\widebar{V}_{0}|=|\widebar{V}_{1}|=(2-\beta+\xi)n$.

Set $\delta=\frac{\xi n}{2\bar{n}}$. Run the algorithm in hypothesis on
$\widebar{G}$ and let $\hat{c}$ and $\mathtt{match}_{\hat{M}}$ be its outputs.
We set $\tilde{c}=\hat{c}-(2-2\beta+\xi)n$. We set
$\tilde{M}:=\hat{M}\cap(V_{0}\times V_{1})$ and implement
$\mathtt{match}_{\tilde{M}}(u)$ as follows. Let
$v\leftarrow\mathtt{match}_{\hat{M}}(u)$. If $v=\bot$, return $\bot$. If
either $u$ or $v$ is dummy, return $\bot$; else return $v$. It is easy to see
that $\widebar{M}^{1}\cap(V_{0}\times V_{1})$ is a min-weight matching of size
$(\beta-\xi)n$ in $G$, hence

$\bar{c}(\widebar{M}^{1})=c(M^{\beta-\xi})+|D_{0}|+|D_{1}|=c(M^{\beta-\xi})+2(1-\beta+\xi)n\leq
c(M^{\beta})+(2-2\beta+\xi)n.$

On the other hand, in $\widebar{M}^{1-\delta}$ at most $2\delta\bar{n}=\xi n$
dummy vertices are left unmathced, so at least $(2-2\beta+\xi)n$ dummy
vertices are matched in $\widebar{M}^{1-\delta}$. Moreover,
$\widebar{M}^{1-\delta}\cap(V_{0}\times V_{1})$ is a matching in $G$ of size
$\geq n-(1-\beta+\xi)n-\delta\bar{n}=(\beta-2\xi)n$. Hence,

$\bar{c}(\widebar{M}^{1-\delta})\geq c(M^{\beta-2\xi})+(2-2\beta+\xi)n\geq
c(M^{\alpha})+(2-2\beta+\xi)n.$

Thus, $\bar{c}(\widebar{M}^{1-\delta})\leq\hat{c}\leq\bar{c}(\widebar{M}^{1})$
implies $c(M^{\alpha})\leq\tilde{c}\leq c(M^{\beta})$.

Now we prove the bounds on $\tilde{M}$. We have that since
$|\hat{M}|\geq(1-\delta)\bar{n}$, then at most $2\delta\bar{n}=\xi n$ dummy
vertices are left unmatched in $\hat{M}$ and so

$\displaystyle c(\tilde{M})$
$\displaystyle\leq\bar{c}(\hat{M})-(2(1-\beta+\xi)n-2\delta\bar{n})$
$\displaystyle\leq\bar{c}(\widebar{M}^{1})-(2-2\beta+\xi)n$
$\displaystyle=c(M^{\beta-\xi})+2(1-\beta-\xi)n-(2-2\beta+\xi)n$
$\displaystyle=c(M^{\beta-\xi})+\xi n\leq c(M^{\beta}).$

Moreover,
$|\tilde{M}|\geq(1-\delta)\bar{n}-2(1-\beta+\xi)n=(\beta-\frac{3}{2}\xi)n\geq\alpha
n$. ∎

Finally, we can prove Theorem 3.

###### Proof of Theorem 3.

We notice that combining Theorem 7 and Theorem 9 we have a sublinear
implementation of Algorithm 1 that takes a graph bipartite graph $G=(V_{0}\cup
V_{1},E)$ and a cost function $c:E\rightarrow[1,C]$ as input, outputs an
estimate $\hat{c}$ and a matching oracle $\mathtt{match}_{\hat{M}}$. The
estimate $\hat{c}$ satisfies $c(M^{1-\delta})\leq\hat{c}\leq c(M^{1})$,
$\hat{M}$ satisfies $|\hat{M}|\geq(1-\delta)n$ and $c(\hat{M})\leq
c(M^{\texttt{OPT}})$. Moreover, such algorithm runs in time
$O(n^{2-\varepsilon})$ and $\mathtt{match}_{\hat{M}}$ runs in time
$O(n^{1+\varepsilon})$ for some $\varepsilon>0$.

Then, combining Lemma 6.3, Lemma 6.2 and Lemma 6.1 we obtain an algorithm that
takes as input a bipartite graph $G=(V_{0}\cup V_{1},E)$ endowed with a cost
function $c:E\rightarrow\mathbb{R}^{+}$, outputs an estimate $\hat{c}$ and a
matching oracle $\mathtt{match}_{\hat{M}}$ such that (whp)
$c(M^{\alpha})\leq\hat{c}\leq c(M^{\beta})$, $|\hat{M}|\geq\alpha n$, and
$c(\hat{M})\leq c(M^{\beta})$. Moreover such algorithm runs in time
$O(n^{2-\varepsilon})$ and $\mathtt{match}_{\hat{M}}$ runs in time
$O(n^{1+\varepsilon})$ for some $\varepsilon>0$. ∎

###  6.2 Proof of Theorem 1 and Corollary 1.1

Since Corollary 1.1 is more general than Theorem 1 we simply prove the former.

See 1.1

Fix a constant $\gamma>0$. From each probability distribution $\mu,\nu$ we
sample (with replacement) a multi-set of $m=\Theta(n\log(n))$ points. We use
$V_{\mu},V_{\nu}$ to denote the respective multi-sets, and
$\hat{\mu},\hat{\nu}$ to denote the empirical distributions of sampling a
random point from $V_{\mu},V_{\nu}$. Let $\mathcal{T}_{\mu},\mathcal{T}_{\nu}$
be the transport plans realizing $\mathrm{EMD}(\mu,\mu^{\prime})$ and
$\mathrm{EMD}(\nu,\nu^{\prime})$ respectively. Namely, $\mathcal{T}_{\mu}$ is
a coupling between $\mu$ and $\mu^{\prime}$ such that
$\mathrm{EMD}(\mu,\mu^{\prime})=E_{(x,y)\sim\mathcal{T}_{\mu}}[d(x,y)]$ and
likewise for $\mathcal{T}_{\nu}$. For each sample $x$ in $\hat{\mu}$ we sample
$x^{\prime}\sim\mathcal{T}(x,\cdot)$ and let $V^{\prime}_{\mu}$ be the multi-
set of samples $x^{\prime}$ for $x\in V_{\mu}$. Define $V^{\prime}_{\nu}$
similarly. Let $\hat{\mu}^{\prime}$ and $\hat{\nu}^{\prime}$ be the empirical
distributions of sampling a random point from $V^{\prime}_{\mu}$ and
$V^{\prime}_{\nu}$.

######  Lemma 6.4.

$\mathrm{EMD}(\hat{\mu},\hat{\mu}^{\prime})\leq\xi+\gamma$ with high
probability.

###### Proof.

$\textnormal{E}[\mathrm{EMD}(\hat{\mu},\hat{\mu}^{\prime})]\leq\textnormal{E}\left[\frac{1}{m}\cdot\sum_{x\in
V_{\mu}}d(x,x^{\prime})\right]=\textnormal{E}_{(x,x^{\prime})\sim\mathcal{T}_{\mu}}[d(x,x^{\prime})]=\mathrm{EMD}(\mu,\mu^{\prime})\leq\xi$.
Moreover,
$\textnormal{Var}_{(x,x^{\prime})\sim\mathcal{T}_{\mu}}[d(x,x^{\prime})]\leq
1$, thus $m=\Theta(n\log n)$ ensures
$\mathrm{EMD}(\hat{\mu},\hat{\mu}^{\prime})\leq\xi+\gamma$ whp. ∎

######  Lemma 6.5.

$\mathrm{EMD}(\hat{\mu}^{\prime},\mu^{\prime})\leq\mathrm{TV}(\hat{\mu}^{\prime},\mu^{\prime})\leq\gamma$
with high probability.

###### Proof.

First, we observe that $V_{\mu}^{\prime}$ is distributed as a multi-set of $m$
samples from $\mu^{\prime}$. For any point $x^{\prime}$ with at least
$(\gamma/4n)$-mass in $\mu^{\prime}$, we expect $\Omega(\log n)$ samples of
$x^{\prime}$ in $V^{\prime}_{\mu}$, so by Chernoff bound we have that with
high probability the number of samples of $x^{\prime}$ concentrates to within
$(1\pm\gamma/4)$-factor of its expectation. Furthermore, with high probability
at most $(\gamma/2)$-fraction of the samples correspond to points with less
than $(\gamma/4n)$-mass in the original distribution. Thus overall, the
empirical distribution $\hat{\mu}^{\prime}$ is within $\gamma$ TV distance of
$\mu^{\prime}$. Finally,
$\mathrm{EMD}(\hat{\mu}^{\prime},\mu^{\prime})\leq\mathrm{TV}(\hat{\mu}^{\prime},\mu^{\prime})$
beacuse $d(\cdot,\cdot)\in[0,1]$. ∎

######  Lemma 6.6.

$\mathrm{EMD}(\mu,\hat{\mu})\leq\xi+2\gamma$ with high probability.

###### Proof.

Combining Lemma 6.4, Lemma 6.5 we obtain the following

$\mathrm{EMD}(\mu,\hat{\mu})\leq\mathrm{EMD}(\mu,\mu^{\prime})+\mathrm{EMD}(\mu^{\prime},\hat{\mu}^{\prime})+\mathrm{EMD}(\hat{\mu}^{\prime},\hat{\mu})\leq
2\xi+2\gamma.$

∎

###### Proof of Corollary 1.1.

We consider the bipartite graph with a vertex for each point in
$V_{\mu},V_{\nu}$ and edge costs induced by $d(\cdot,\cdot)$. We apply the
algorithm guaranteed by Theorem 3 to find an estimate of the min-weight
matching over between $(1-\gamma)m$ and $m$ vertices. We return the cost
estimate $\widehat{\mathrm{EMD}}$ on the bipartite graph (normalized by
dividing by $m$). Theorem 3 guarantees that
$\widehat{\mathrm{EMD}}\in[\mathrm{EMD}(\hat{\mu},\hat{\nu})\pm\gamma]$. Then
using triangle inequality on $\mathrm{EMD}$, as well as Lemma 6.6 on both
$\mu$ and $\nu$ we obtain

$\left|\widehat{\mathrm{EMD}}-\mathrm{EMD}(\mu,\nu)\right|\leq\left|\widehat{\mathrm{EMD}}-\mathrm{EMD}(\hat{\mu},\hat{\nu})\right|+\mathrm{EMD}(\mu,\hat{\mu})+\mathrm{EMD}(\nu,\hat{\nu})\leq
4\xi+5\gamma.$

Scaling $\gamma$ down of a factor $5$ we retireve Corollary 1.1. ∎

###  6.3 Proof of Theorem 2

See 2

###### Proof.

Let $M$ be the maximum matching in $G$ with total cost at most $B$, and let
$|M|=\xi n$. We perform a binary search for $\xi$ using the algorithm from
Theorem 3 as a subroutine. This loses only a factor $\log(n)$ in query
complexity, which gets absorbed in $O(n^{2-\varepsilon})$ by choosing a
suitable constant $\varepsilon$. ∎

#### Acknowledgments.

We thank Erik Waingarten for inspiring discussions. We thank Tal Herman and
Greg Valiant for pointing out the sample complexity lower bound implied by
[VV10].

## References

  * [ACB17] Martin Arjovsky, Soumith Chintala and Léon Bottou  “Wasserstein generative adversarial networks”  In _International conference on machine learning_ , 2017, pp. 214–223  PMLR
  * [Aga+22] Pankaj K Agarwal, Hsien-Chih Chang, Sharath Raghvendra and Allen Xiao  “Deterministic, near-linear $(1+\epsilon)$-approximation algorithm for geometric bipartite matching”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 1052–1065
  * [AIK08] Alexandr Andoni, Piotr Indyk and Robert Krauthgamer  “Earth mover distance over high-dimensional spaces.”  In _SODA_ 8, 2008, pp. 343–352
  * [ALT21] Tenindra Abeywickrama, Victor Liang and Kian-Lee Tan  “Optimizing bipartite matching in real-world applications by incremental cost computation”  In _Proceedings of the VLDB Endowment_ 14.7 VLDB Endowment, 2021, pp. 1150–1158
  * [And+09] Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff  “Efficient sketches for earth-mover distance, with applications”  In _2009 50th Annual IEEE Symposium on Foundations of Computer Science_ , 2009, pp. 324–330  IEEE
  * [And+14] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak and Grigory Yaroslavtsev  “Parallel algorithms for geometric graph problems”  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , 2014, pp. 574–583
  * [ANR17] Jason Altschuler, Jonathan Niles-Weed and Philippe Rigollet  “Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration”  In _Advances in neural information processing systems_ 30, 2017
  * [AS14] Pankaj K Agarwal and R Sharathkumar  “Approximation algorithms for bipartite matching with metric and geometric costs”  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , 2014, pp. 555–564
  * [AZ23] Alexandr Andoni and Hengjie Zhang  “Sub-quadratic (1+$\backslash$eps)-approximate Euclidean Spanners, with Applications”  In _arXiv preprint arXiv:2310.05315_ , 2023
  * [Ba+11] Khanh Do Ba, Huy L Nguyen, Huy N Nguyen and Ronitt Rubinfeld  “Sublinear time algorithms for earth mover’s distance”  In _Theory of Computing Systems_ 48 Springer, 2011, pp. 428–442
  * [Bac+20] Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razenshteyn and Tal Wagner  “Scalable nearest neighbor search for optimal transport”  In _International Conference on machine learning_ , 2020, pp. 497–506  PMLR
  * [Băd+05] Mihai Bădoiu, Artur Czumaj, Piotr Indyk and Christian Sohler  “Facility location in sublinear time”  In _Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings 32_ , 2005, pp. 866–877  Springer
  * [Beh+23] Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein and Amin Saberi  “Beating greedy matching in sublinear time”  In _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2023, pp. 3900–3945  SIAM
  * [Beh22] Soheil Behnezhad  “Time-optimal sublinear algorithms for matching and vertex cover”  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 873–884  IEEE
  * [BKS23] Sayan Bhattacharya, Peter Kiss and Thatchaphol Saranurak  “Dynamic $(1+\epsilon)$-Approximate Matching Size in Truly Sublinear Update Time”  In _arXiv preprint arXiv:2302.05030_ , 2023
  * [BKS23a] Sayan Bhattacharya, Peter Kiss and Thatchaphol Saranurak  “Sublinear Algorithms for (1.5+$\epsilon$)-Approximate Matching”  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023_ ACM, 2023, pp. 254–266  DOI: 10.1145/3564246.3585252
  * [Bla+18] Jose Blanchet, Arun Jambulapati, Carson Kent and Aaron Sidford  “Towards optimal running times for optimal transport”  In _arXiv preprint arXiv:1810.07717_ , 2018
  * [BRR23] Soheil Behnezhad, Mohammad Roghani and Aviad Rubinstein  “Sublinear time algorithms and complexity of approximate maximum matching”  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , 2023, pp. 267–280
  * [Can20] Clément L Canonne  “A survey on distribution testing: Your data is big. But is it blue?”  In _Theory of Computing_ Theory of Computing Exchange, 2020, pp. 1–100
  * [Cha+23] Moses Charikar, Beidi Chen, Christopher Ré and Erik Waingarten  “Fast Algorithms for a New Relaxation of Optimal Transport”  In _The Thirty Sixth Annual Conference on Learning Theory_ , 2023, pp. 4831–4862  PMLR
  * [Cha02] Moses S Charikar  “Similarity estimation techniques from rounding algorithms”  In _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_ , 2002, pp. 380–388
  * [Che+22] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva  “Maximum flow and minimum-cost flow in almost-linear time”  In _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 612–623  IEEE
  * [Che+22a] Xi Chen, Rajesh Jayaram, Amit Levi and Erik Waingarten  “New streaming algorithms for high dimensional EMD and MST”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 222–233
  * [CS09] Artur Czumaj and Christian Sohler  “Estimating the weight of metric minimum spanning trees in sublinear time”  In _SIAM Journal on Computing_ 39.3 SIAM, 2009, pp. 904–922
  * [Cut13] Marco Cuturi  “Sinkhorn distances: Lightspeed computation of optimal transport”  In _Advances in neural information processing systems_ 26, 2013
  * [DGK18] Pavel Dvurechensky, Alexander Gasnikov and Alexey Kroshnin  “Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm”  In _International conference on machine learning_ , 2018, pp. 1367–1376  PMLR
  * [FL22] Kyle Fox and Jiashuai Lu  “A deterministic near-linear time approximation scheme for geometric transportation”  In _arXiv preprint arXiv:2211.03891_ , 2022
  * [GT89] Harold N Gabow and Robert E Tarjan  “Faster scaling algorithms for network problems”  In _SIAM Journal on Computing_ 18.5 SIAM, 1989, pp. 1013–1036
  * [HIS13] Sariel Har-Peled, Piotr Indyk and Anastasios Sidiropoulos  “Euclidean spanners in high dimensions”  In _Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms_ , 2013, pp. 804–809  SIAM
  * [Ind03] Piotr Indyk  “Fast color image retrieval via embeddings”  In _Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003_ , 2003
  * [Ind04] Piotr Indyk  “Algorithms for dynamic geometric problems over data streams”  In _Proceedings of the thirty-sixth annual ACM Symposium on Theory of Computing_ , 2004, pp. 373–380
  * [Kuh55] Harold W Kuhn  “The Hungarian method for the assignment problem”  In _Naval research logistics quarterly_ 2.1-2 Wiley Online Library, 1955, pp. 83–97
  * [Kus+15] Matt Kusner, Yu Sun, Nicholas Kolkin and Kilian Weinberger  “From word embeddings to document distances”  In _International conference on machine learning_ , 2015, pp. 957–966  PMLR
  * [Le+21] Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui and Nhat Ho  “On robust optimal transport: Computational complexity and barycenter computation”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 21947–21959
  * [LMR19] Nathaniel Lahn, Deepika Mulchandani and Sharath Raghvendra  “A graph theoretic additive approximation of optimal transport”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [LXH23] Yiling Luo, Yiling Xie and Xiaoming Huo  “Improved Rate of First Order Algorithms for Entropic Optimal Transport”  In _International Conference on Artificial Intelligence and Statistics_ , 2023, pp. 2723–2750  PMLR
  * [McG05] Andrew McGregor  “Finding graph matchings in data streams”  In _International Workshop on Approximation Algorithms for Combinatorial Optimization_ , 2005, pp. 170–181  Springer
  * [PC19] Gabriel Peyré and Marco Cuturi  “Computational optimal transport: With applications to data science”  In _Foundations and Trends® in Machine Learning_ 11.5-6 Now Publishers, Inc., 2019, pp. 355–607
  * [Pha+20] Khiem Pham, Khang Le, Nhat Ho, Tung Pham and Hung Bui  “On unbalanced optimal transport: An analysis of sinkhorn algorithm”  In _International Conference on Machine Learning_ , 2020, pp. 7673–7682  PMLR
  * [Roh19] Dhruv Rohatgi  “Conditional hardness of earth mover distance”  In _arXiv preprint arXiv:1909.11068_ , 2019
  * [RTG00] Yossi Rubner, Carlo Tomasi and Leonidas J Guibas  “The earth mover’s distance as a metric for image retrieval”  In _International journal of computer vision_ 40 Springer, 2000, pp. 99–121
  * [SA12] R Sharathkumar and Pankaj K Agarwal  “A near-linear time $\varepsilon$-approximation algorithm for geometric bipartite matching”  In _Proceedings of the forty-fourth annual ACM symposium on Theory of computing_ , 2012, pp. 385–394
  * [San15] Filippo Santambrogio  “Optimal transport for applied mathematicians”  In _Birkäuser, NY_ 55.58-63 Springer, 2015, pp. 94
  * [Sol+15] Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du and Leonidas Guibas  “Convolutional wasserstein distances: Efficient optimal transportation on geometric domains”  In _ACM Transactions on Graphics (ToG)_ 34.4 ACM New York, NY, USA, 2015, pp. 1–11
  * [Vil+09] Cédric Villani  “Optimal transport: old and new”  Springer, 2009
  * [VV10] Gregory Valiant and Paul Valiant  “A CLT and tight lower bounds for estimating entropy.”  In _Electron. Colloquium Comput. Complex._ 17, 2010, pp. 179
  * [Yur+19] Mikhail Yurochkin, Sebastian Claici, Edward Chien, Farzaneh Mirzazadeh and Justin M Solomon  “Hierarchical optimal transport for document representation”  In _Advances in neural information processing systems_ 32, 2019