# Geometric Bipartite Matching is in NC

Sujoy Bhore Sarfaraz Equbal Rohit Gurjar Department of Computer Science &
Engineering, Indian Institute of Technology Bombay, India.
Email<EMAIL_ADDRESS>of Computer Science & Engineering,
Indian Institute of Technology Bombay, India.
Email<EMAIL_ADDRESS>of Computer Science & Engineering,
Indian Institute of Technology Bombay, India.
Email<EMAIL_ADDRESS>supported by SERB MATRICS grant MTR/2022/001009

###### Abstract

In this work, we study the parallel complexity of the Euclidean minimum-weight
perfect matching (EWPM) problem. Here our graph is the complete bipartite
graph $G$ on two sets of points $A$ and $B$ in $\mathbb{R}^{2}$ and the weight
of each edge is the Euclidean distance between the corresponding points. The
weighted perfect matching problem on general bipartite graphs is known to be
in RNC [Mulmuley, Vazirani, and Vazirani, 1987], and Quasi-NC [Fenner, Gurjar,
and Thierauf, 2016]. Both of these results work only when the weights are of
$O(\log n)$ bits. It is a long-standing open question to show the problem to
be in NC.

First, we show that for EWPM, a linear number of bits of approximation is
required to distinguish between the minimum-weight perfect matching and other
perfect matchings. Next, we show that the EWPM problem that allows up to
$\frac{1}{\operatorname{poly}(n)}$ additive error, is in NC.

##  1 Introduction

The perfect matching problem is one of the well-studied problems in Complexity
theory, especially, in the context of derandomization and parallelization.
Given a graph $G=(V,E)$, the problem asks, whether the graph contains a
matching that matches every vertex of $G$. Due to Edmonds [Edm65], the problem
is known to be solvable in polynomial time. However, the parallel complexity
of the problem has not been completely resolved till today. In 1979, Lovász
[Lov79] showed that perfect matching can be solved by efficient randomized
parallel algorithms, i.e., the problem is in RNC. Hence, the main question,
with respect to its parallel complexity, is whether this randomness is
necessary, i.e., whether the problem is in NC111The class NC represents the
problems that have efficient parallel algorithms, i.e., they have uniform
circuits of polynomial size and $\operatorname{polylog}$ depth.

The search version of the problem asks to explicitly construct a perfect
matching in a graph if one exists. Note that in the parallel setting, there is
no obvious reduction from search to decision. This version is also known to be
in RNC [KUW85, MVV87]. The Mulmuley-Vazirani-Vazirani (MVV) algorithm [MVV87],
in fact, also works for the weighted version of the problem, where there is a
polynomially bounded weight assignment given on the edges of the graph.

The MVV algorithm [MVV87] introduced the celebrated _Isolation lemma_. A
weight assignment is called _isolating_ for a graph $G$, if the minimum weight
perfect matching in $G$ is unique, if one exists. Mulmuley, Vazirani, and
Vazirani [MVV87] showed that given an isolating weight assignment with
polynomially bounded integer weights for a graph $G$, a perfect matching in
$G$ can be constructed in NC. The only place where they use randomization is
to get an isolating weight assignment. Their Isolation lemma states that a
random weight assignment is isolating!

_Derandomizing_ the Isolation lemma means to construct such a weight
assignment deterministically in NC. A line of work derandomized the Isolation
Lemma for special families of graphs, e.g., planar bipartite graphs [DKR10,
TV12], strongly chordal graphs [DK98], graphs with a small number of perfect
matchings [GK87]. In 2016, Fenner, Gurjar, and Thierauf [FGT16] showed that
the bipartite perfect matching problem is in quasi-NC, by an almost complete
derandomization of the Isolation Lemma. Later, Svensson and Tarnawski [ST17]
showed that the problem in general graphs is also in Quasi-NC. Subsequently,
Anari and Vazirani [AV20] gave an NC algorithm for finding perfect matching in
general planar graphs. All of these algorithms work for the weighted version
(poly-bounded) of the problem as well.

What remains a challenging open question is to find an NC algorithm for any
versions (decision/search/weighted) of the perfect matching problem, even for
bipartite graphs. Inspired by the positive results on planar bipartite graphs,
we investigate the weighted version of the perfect matching problem in the
geometric setting (2 dimensional).

#### Geometric Bipartite Matching.

Let $A$ and $B$ be two point sets in $\mathbb{R}^{2}$ of size $n$ each.
Consider the complete bipartite graph $G(A,B,E)$ with the following cost
function on the edges: for any edge $e=(a,b)$, define
$\mathcal{C}(e)=||a-b||$, where $||\cdot||$ denotes the Euclidean norm. In
other words, we consider the Euclidean distance between the endpoints as the
cost of an edge. The cost of a perfect matching $M$ is the sum of its edge
costs $\mathcal{C}(M)=\Sigma_{e\in M}\mathcal{C}(e)$. The Euclidean minimum-
weight perfect matching (EWPM) problem is to find
$M_{opt}=\operatorname{argmin}_{|M|=n}\mathcal{C}(M)$, that is, the optimal
perfect matching with respect to function $\mathcal{C}$. EWPM is a fundamental
problem in Computational Geometry and has been studied extensively over the
years. See Section 1.2 for an overview of the results. In this work, we focus
on the parallel complexity of EWPM problem, and ask the following question -

######  Question 1.

Is EWPM in NC?

Optimization problems in computational geometry are usually studied in real
arithmetic computational model, where comparing two distances or sums of
distances is assumed to be a unit cost operation. However, in the bit
complexity model, it is not clear if distances, which can be irrational
numbers, can be efficiently added or compared. In fact, the problem of
comparing a two sums of square roots is not known to be in P (see, for
example, [O’R81, TOP]). See [EHS23] for some recent progress on the sum of
square roots problem.

Our path towards showing an NC algorithm for EWPM naturally goes via the MVV
algorithm. Recall that the MVV algorithm works only when the given
weights/costs are polynomially bounded integers, because in intermediate
steps, it needs to put weights in the exponent. Hence, inevitably we need to
consider the bit complexity of the weights. Note that there are other parallel
algorithms for the weighted perfect matching problem (e.g., [GPST92]), but
there too it is important that the weights are polynomially bounded integers.

It is not clear if the EWPM problem is in P (or even in NP) in the bit-
complexity model. To the best of our knowledge, the existing algorithms for
EWPM require the comparison between two sums of square roots. This naturally
leads us to consider an approximate version of the problem. Let us define the
$\delta$-EWPM problem, which asks for the Euclidean minimum-weight perfect
matching up to an additive error $\delta$. We aim to get an NC algorithm for
the problem whenever $1/\delta$ is $\operatorname{poly}(n)$.

###  1.1 Our Contribution

In this work, we study the parallel complexity of $\delta$-EWPM problem.
First, it is natural to ask whether solving $\delta$-EWPM for some
$\delta=1/\operatorname{poly}(n)$ will already solve the EWPM problem. In
other words, by considering $O(\log n)$ bit approximations of Euclidean
distances, can we hope to find the Euclidean minimum weight perfect matching?
Our first result rules out this possibility. We show that for EWPM, a super-
linear number of bit approximations is required to distinguish the minimum-
weight perfect matching from others.

######  Theorem 1.

There is a set of $2n$ points in the $O(n^{5})\times O(n^{5})$ integer grid
such that in the corresponding complete bipartite graph, the difference
between the weights of the minimum weight perfect matching and another perfect
matching is at most $1/(n-1)!$.

This theorem is proved in Section 2.

Next, we come to our positive result. We affirmatively answer Question 1, by
showing that the Euclidean minimum weight perfect matching problem that allows
up to $\frac{1}{\operatorname{poly}(n)}$ error, is in NC.

######  Theorem 2.

The $\delta$-EWPM is in NC, when $1/\delta$ is $\operatorname{poly}(n)$ and
the points are on a polynomially bounded integer grid.

This theorem is proved in Section 3.

###  1.2 Related Work

The classical Hopcroft-Karp algorithm computes a maximum-cardinality matching
in a bipartite graph with $n$ vertices and $m$ edges in $O(m\sqrt{n})$ time
[HK73]. After almost three decades, Madry [Mad13] improved the running time to
$O(m^{10/7}\operatorname{polylog}n)$ time, which was further improved to
$O(m+n^{3/2}\operatorname{polylog}n)$ by Brand et al. [vdBLN+20]. The
Hungarian algorithm computes the minimum-weight maximum cardinality matching
in $O(mn+n^{2}\log n)$ time [PS98]. In a recent breakthrough, Brand et al.
[VDBCP+23] showed that maximum-cardinality matching in bipartite graphs, can
be solved in near-linear time.

For two sets of points $A$ and $B$ in $\mathbb{R}^{2}$, the best known
algorithm for computing EWPM runs in $O(n^{2}\operatorname{polylog}n)$ time
[ACX19, AES95]. Moreover, if points have integer coordinates bounded by
$\Delta$, the running time can be improved to
$O(n^{3/2}\operatorname{polylog}n\log\Delta)$ [Sha13]. If coordinates of input
points have real values, it is not known whether a subquadratic algorithm
exists for computing EMWM. However, for the non-bipartite case, Varadarajan
[Var98] presented an $O(n^{3/2}\operatorname{polylog}n)$-time algorithm under
any $\ell_{p}$-norm. For bipartite matching, a large body of literature
focused on obtaining approximate matching for points in $\mathbb{R}^{d}$.
Varadarajan and Agarwal [VA99] presented an
$O(n^{3/2}\varepsilon^{-d}\log^{d}n)$-time $\varepsilon$-approximation
algorithm for computing EWPM of points lying in $\mathbb{R}^{d}$. Later,
Agarwal and Raghavendra [SA12] improved the running time. Recently, Agarwal et
al. [ACRX22] presented a deterministic algorithm with running time
$n\cdot(\varepsilon^{-1}\log n)^{O(d)}$ time, and computes a perfect matching
whose cost is within a $(1+\varepsilon)$ factor of the optimal matching under
any $\ell_{p}$-norm.

##  2 Lower Bound

In this section, we want to show that for a geometric bipartite graph with
$n+n$ vertices, we need at least $\Omega(n\log n)$ bits of precision to
distinguish the minimum weight perfect matching from others. We will show this
by constructing a bipartite set of $2n$ points in the integer grid of size
$O(n^{5})\times O(n^{5})$ such that the difference between the weights of the
minimum weight perfect matching and the one with the next higher weight will
be $1/(n-1)!$. Towards this, the first step is to construct a geometric graph
where there are two perfect matchings whose weights differ by at most
$1/(n-1)!$ (Claim 2). Here we use an argument based on the pigeonhole
principle. A similar argument was used to show such a bound on the difference
of two sums of square roots [CL10].

In the above construction, it is not necessary that one of the two perfect
matchings is of minimum weight. In the second step, we show that the above
geometric graph can be modified to construct another one where the same two
perfect matchings appear, but now one of them is of minimum weight (Claim 4).

######  Construction 1.

Consider the left hand side vertices $u_{0},u_{1},\dots,u_{n-1}$ at points

$\\{(0,0),(0,1),(0,2),\dots,(0,n-1)\\}.$

Similarly, consider the right hand side vertices $v_{0},v_{1},\dots,v_{n-1}$
at points

$\\{(q,n),(q,2n),(q,3n),\dots,(q,n^{2})\\},$

where $q=n^{4}$.

######  Claim 1.

The geometric bipartite graph in Construction 1 has all its perfect matchings
with distinct weights.

###### Proof.

Now, we will show that weights of any two distinct perfect matchings are
different. Recall that edge weights are square roots of integers. We will
argue that the edge weights are linearly independent over rationals, which
immediately implies that any two different subsets of edges cannot have equal
weights. It is known that to show linear independence of a set of square roots
of integers, it suffices to show that they are _pairwise_ linearly independent
(see, for example, [CO07]). So, now we just argue that the edge weights are
pairwise linearly independent.

For the sake of contradiction, suppose we have two edges $e$ and $e^{\prime}$,
whose weights are linearly dependent. Then we have $aw(e)=bw(e^{\prime})$ for
some integers $a$ and $b$. From here we get that
$w(e)^{2}w(e^{\prime})^{2}=(a/b)^{2}w(e)^{4}$. That is, the product
$w(e)^{2}w(e^{\prime})^{2}$ is square of a rational number. Since it is an
integer, it must be square of an integer. From our construction, for any edge
$e$, we have $q\leq w(e)\leq\sqrt{q^{2}+n^{4}}$. Hence,
$w(e)^{2}w(e^{\prime})^{2}$ must be square of an integer which between $q^{2}$
and $q^{2}+n^{4}$. Moreover, we notice that only one edge, $e$ or
$e^{\prime}$, can be equal to $\sqrt{q^{2}+n^{4}}$. So we can write
$w(e)^{2}w(e^{\prime})^{2}=(q^{2}+\alpha)^{2}$ for some integer
$0\leq\alpha<n^{4}$.

For any edge $e$, let us denote by $\Delta_{e}$, the difference in the $y$
coordinates of the two endpoints of the edge. Then, the weight of an edge $e$
can be written as $w(e)=\sqrt{q^{2}+\Delta_{e}^{2}}$. Now, we have

$w(e)^{2}w(e^{\prime})^{2}=(q^{2}+\Delta_{e}^{2})(q^{2}+\Delta_{e^{\prime}}^{2})=(q^{2}+\alpha)^{2}.$

Equivalently,

$q^{2}(\Delta_{e}^{2}+\Delta_{e^{\prime}}^{2})+\Delta_{e}^{2}\Delta_{e^{\prime}}^{2}=2q^{2}\alpha+\alpha^{2}.$

Observe that $\Delta_{e}^{2}\Delta_{e^{\prime}}^{2}<n^{8}=q^{2}$ (from
construction as both $\Delta_{e}$ and $\Delta_{e^{\prime}}$ can not be equal
to $n^{2}$) and also $\alpha^{2}<n^{8}=q^{2}$. Hence, we conclude from above
that

$\Delta_{e}^{2}+\Delta_{e^{\prime}}^{2}=2\alpha\text{ and
}\Delta_{e}^{2}\Delta_{e^{\prime}}^{2}=\alpha^{2}.$

This implies that $\Delta_{e}=\Delta_{e^{\prime}}$.

Now, we will argue that for any two distinct edges, we have
$\Delta_{e}\neq\Delta_{e^{\prime}}$, which will give us a contradiction.
Indeed for the edge $(u_{i},v_{j})$, we have $\Delta_{e}=jn-i$, which comes
from a unique choice of $0\leq i\leq n-1$ and $1\leq j\leq n$.

∎

######  Claim 2.

In the geometric bipartite graph from Construction 1, there are two perfect
matchings whose weights are different and differ by at most $1/(n-1)!$.

###### Proof.

From Claim 1, all $n!$ perfect matchings have distinct weights. From the
construction, any perfect matching has its weight between $n^{5}$ and
$n\sqrt{n^{8}+n^{4}}\leq n(n^{4}+1)$. The bound follows from the pigeonhole
principle. ∎

Now, consider the two perfect matchings from Claim 2, say $M_{1}$ and $M_{2}$,
whose weights differ by at most $1/(n-1)!$ . Let $M_{1}$ be the one with a
smaller weight. The union of two perfect matchings $M_{1}\cup M_{2}$ is a set
of vertex-disjoint cycles and edges. We are going to ignore the common edges
between $M_{1}$ and $M_{2}$. Let $(e_{1},e_{2},\dots,e_{2\ell})$ be the
sequence of edges generated from the cycles in $M_{1}\cup M_{2}$ as follows:
arrange the cycles in an arbitrary order. For each cycle, start from that edge
in $M_{1}$ which has its left endpoint with minimum $y$-coordinate, and
traverse along the cycle till we hit the starting vertex. Note that the
sequence $(e_{1},e_{2},\dots,e_{2\ell})$ has edges alternating from $M_{1}$
and $M_{2}$. The new graph will be constructed by “unrolling” these cycles.
The construction will be such that edges outside these cycles will be long,
and hence, will not be a part of any minimum weight perfect matching. Recall
that for any edge $e=(u_{i},v_{j})$ (Construction 1), we denote by
$\Delta_{e}$ the difference in the $y$-coordinates of the endpoints, i.e.,
$jn-i$.

######  Construction 2.

Consider the vertex $t_{0}$ at $(0,0)$. Let $y_{0}=0$. For $1\leq k\leq
2\ell$, we place the vertex $t_{k}$ at $(kq,y_{k})$, where

  * •

$y_{k}=y_{k-1}+\Delta_{e_{k}}$ if $k$ is odd

  * •

$y_{k}=y_{k-1}-\Delta_{e_{k}}$ if $k$ is even

We add three more vertices: $s_{0}$ at $(0,-2\ell q)$, $s_{1}$ at $(\ell
q,-2\ell q)$, and $s_{2}$ at $(2\ell q,-2\ell q)$. See Figure 1.

$0$$q$$e_{1}$$e_{3}$$e_{2}$$e_{4}$$0$$q$$2q$$3q$$4q$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$s_{0}$$s_{1}$$s_{2}$
Figure 1: The left hand side figure shows a cycle in the union of two perfect
matchings. The right hand side figure shows how we “unroll” this cycle.

Corresponding to perfect matchings $M_{1}$ and $M_{2}$, here we will have
prefect matchings $M_{1}^{\prime}$ and $M_{2}^{\prime}$ as

$M_{1}^{\prime}=\\{e_{1},e_{3},\dots,e_{2\ell-1},(t_{2\ell},s_{2}),(s_{0},s_{1})\\}$
$M_{2}^{\prime}=\\{e_{2},e_{4},\dots,e_{2\ell},(t_{0},s_{0}),(s_{1},s_{2})\\}.$

The following are easy observations about Construction 2.

  1. (I)

The edge lengths of $e_{1},e_{2},\dots,e_{2\ell}$ are exactly same as their
lengths in Construction 1.

  2. (II)

$y_{k}\geq 0$ for each $1\leq k\leq 2\ell$, because for each cycle, the cycle
traversal starts from the lowest $y$ coordinate on the left. Moreover,
$y_{2\ell}$ must be zero, because any cycle traversal ends at the starting
vertex.

  3. (III)

Any pair of vertices are at least distance $q$ apart.

  4. (IV)

$w(M_{1}^{\prime})=w(M_{1})+3\ell q$ and $w(M_{2}^{\prime})=w(M_{2})+3\ell q$.

######  Claim 3.

The minimum weight perfect matching in Construction 2 is $M_{1}^{\prime}$,
with weight $w(M_{1})+3\ell q$.

###### Proof.

Recall that weight of any edge $e_{k}$ is at most
$\sqrt{q^{2}+n^{4}}=\sqrt{n^{8}+n^{4}}\leq n^{4}+1/2=q+1/2$. Hence,
$w(M^{\prime}_{1})\leq\ell(q+1/2)+3\ell q=\ell(4q+1/2)$. We have already
assumed that $M_{2}^{\prime}$ has weight higher than $M^{\prime}_{1}$. Now,
consider any perfect matching $M$ other than $M^{\prime}_{1}$ and
$M_{2}^{\prime}$. We will consider different cases and argue that in each case
$M$ has a larger weight.

  * •

If $M$ matches $s_{1}$ with one of the $t_{k}$ vertices, the weight of that
edge will be at least $2\ell q$. The vertices $s_{0}$ and $s_{2}$ will either
match with each other or to some $t_{k}$ vertices. In either case, they will
contribute at least $2\ell q$ to the weight. The remaining vertices must have
at least $\ell-3$ edges, each with weight at least $q$. Hence, the total
weight will be at least $5\ell q-3q$, which is larger than
$w(M^{\prime}_{1})$.

  * •

Consider the case when $M$ has $(s_{1},s_{2})$ (the other case is similar) and
$s_{0}$ is matched with one of the $t_{k}$ vertices, other than $t_{0}$.
Recall that $y_{k}\geq 0$ and $s_{0}=(0,-2\ell q)$. Then the weight of
$(s_{0},t_{k})$ (for $k>0$) is at least $\sqrt{4\ell^{2}q^{2}+q^{2}}\geq 2\ell
q+q/(4\ell)$. The remaining $2\ell$ vertices will have $\ell$ matching edges,
each with weight at least $q$. Hence, the weight of the matching $M$ will be
at least $\ell q+2\ell q+q/(4\ell)+q\ell$. This is clearly larger than
$w(M^{\prime}_{1})\leq 4\ell q+\ell/2$ (as $q=n^{4}$ and $\ell\leq n$).

  * •

Consider the case when $M$ has $(s_{1},s_{2})$ and $(s_{0},t_{0})$. These two
edges will add up to weight $3\ell q$. Since the matching $M$ is different
from $M^{\prime}_{1}$ and $M^{\prime}_{2}$, it must match a vertex $t_{k}$
with another vertex $t_{j}$ such that $j\neq\\{k-1,k+1\\}$. Then $\lvert
j-k\rvert$ must be at least $3$, because the graph is bipartite. The edge
$(t_{k},t_{j})$ will have weight at least $3q$. The other $\ell-1$ edges will
have weight at least $q$. Hence, the total weight is at least $4\ell q+2q$,
which is again larger than $w(M_{1}^{\prime})$.

  * •

The other cases when $M$ has $(s_{0},s_{1})$ matched are similar to the above
two cases.

∎

Now, we finally come to our main claim.

######  Claim 4.

In the geometric bipartite graph from Construction 2, the difference between
the minimum weight perfect matching and the perfect matching with the next
higher weight is at most $1/(n-1)!$.

###### Proof.

From Claim 3, we know that $M_{1}^{\prime}$ is the minimum weight perfect
matching. We had observed that
$w(M_{1}^{\prime})-w(M_{2}^{\prime})=w(M_{1})-w(M_{2})$. From Claim 2, this
difference is at most $1/(n-1)!$. ∎

##  3 Geometric Bipartite Matching

In this section, we study the parallel complexity of $\delta$-EWPM, and show
that the problem lies in the class NC, for $\delta=1/\operatorname{poly}(n)$.

First of all, we assume that no three vertex points are colinear. There is a
simple fix to break colinearity by way of small perturbations in coordinates.
Specifically, for the $i$th vertex at point $(x_{i},y_{i})$, let us assign its
new coordinates to be $(x_{i}+i/K,y_{i}+i^{2}/K)$, where $K$ is a large enough
number. This specific perturbation guarantees that no three points are
colinear. To see this, consider $i$th, $j$th, and $k$th vertices after the
perturbation. They will be colinear if and only if the following matrix has
zero determinant.

$\begin{pmatrix}1&1&1\\\ x_{i}+i/K&x_{j}+j/K&x_{k}+k/K\\\
y_{i}+i^{2}/K&y_{j}+j^{2}/K&y_{k}+k^{2}/K\end{pmatrix}$

Consider the coefficient of the term $1/K^{2}$ in the determinant, which is
$(i-j)(j-k)(k-i)\neq 0$. Other terms in the determinant will be an integer
multiple of $1/K$ and hence, cannot cancel this term, when $K$ is large enough
($\operatorname{poly}(n)$). This perturbation can cause additive error in the
weights of perfect matchings, but the error will remain bounded by
$O(n^{3}/K)$. Thus, the minimum weight perfect matching with respect to
perturbed coordinates will be an EWPM up to a $1/\operatorname{poly}(n)$
additive error. To make the coordinate integral, we can multiply them by $K$.
Now, give a brief overview of our ideas.

Our main idea is to design an isolating weight assignment for the given graph
and then use the MVV algorithm. Let $G$ be a complete bipartite graph of two
sets of points $A$ and $B$ in $\mathbb{R}^{2}$. The MVV theorem asserts that
if a graph has an isolating weight assignment, then the task of finding the
minimum weight perfect matching in $G$ can be accomplished in NC.

To construct an isolating weight assignment, we adopt the weight scheme
introduced by Tewari and Vinodchandran [TV12], which was designed specifically
for planar bipartite graphs. However, note that our graph is the complete
bipartite graph and hence, far from planar. Our first key observation is that
the union of minimum weight perfect matchings (with respect to Euclidean
distances or even approximate distances) forms a planar subgraph. Then one can
hope to use the Tewari and Vinodchandran [TV12] weight scheme on this planar
subgraph. However, we cannot really compute this planar subgraph (i.e., the
union of minimum weight perfect matchings). What proves to be useful is the
fact that the Tewari-Vinodchandran weight scheme is black-box, i.e, it does
not care what is the underlying planar graph, it only needs to know the points
in the plane where vertices are situated. Finally, we combine the approximate
distance function with the Tewari-Vinodchandran weight function on a smaller
scale, and apply it on the complete bipartite graph. We show that this
combined weight function is indeed isolating.

Towards showing the planarity of the union of minimum weight perfect
matchings, first we establish a simple fact that for any convex quadrilateral,
there is a significant difference between the sum of diagonals and the sum of
any opposite sides.

######  Lemma 1.

Consider a convex quadrilateral formed by a quadruple in an integer grid of
size $N\times N$. The sum of lengths of its diagonals is larger than the sum
of any two opposite sides. And the gap between the two sums is at least
$\frac{1}{4N^{4}}$.

$A$$B$$P$$C$$D$$O$ Figure 2: A convex quadrilateral with its two diagonals.

###### Proof.

Intuitively, the sum of the diagonals will be larger than the sum of any two
opposite sides because of triangle inequality (the diagonals combined with any
two opposite edges form two triangles). The significance of this gap arises
from the fact that if the points are from a grid and are not collinear, then
the angle between any side and the diagonal cannot be infinitely small.
Formally, Let the four corners of the quadrilateral be $A,B,C,D$ (in cyclic
order). See Figure 2. Let $O$ be the intersection point of the diagonals $AC$
and $BD$ (diagonals always intersect in a convex quadrilateral). By triangle
inequality, we have $\lvert AO\rvert+\lvert OB\rvert\geq AB$ and $\lvert
CO\rvert+\lvert OD\rvert\geq CD$. Adding the two we get,

$\lvert AD\rvert+\lvert BC\rvert\geq\lvert AB\rvert+\lvert CD\rvert.$

Now, we lower bound the gap. Let $OP$ be the perpendicular from $O$ to the
line $AB$. And let $\theta$ be the angle $\angle OAP$.

$\lvert AO\rvert-\lvert AP\rvert=\lvert AP\rvert(\sec\theta-1)\geq\lvert
AP\rvert\tan^{2}\theta/2.$ (1)

Let us lower bound $\tan\theta$ for $\theta$ being the angle between any three
non-colinear points on the $N\times N$ grid. Without loss of generality let
$\theta$ be the angle between the integer vectors $(i,j)$ and $(k,\ell)$. The
we can write

$\tan^{2}\theta=1-\cos^{2}\theta=1-\frac{(ik+jl)^{2}}{(i^{2}+j^{2})(k^{2}+\ell^{2})}\geq\frac{(i\ell-
jk)^{2}}{(i^{2}+j^{2})(k^{2}+\ell^{2})}\geq\frac{1}{4N^{4}}.$

The last inequality follows because $i,j,k,l\leq N$ and the difference $i\ell-
jk$, being integral, is at least one. From equation (1), we get $\lvert
AO\rvert-\lvert AP\rvert\geq\lvert AP\rvert/(8N^{4})$. Similarly, we can write
$\lvert BO\rvert-\lvert BP\rvert\geq\lvert BP\rvert/(8N^{4})$. Adding these
two we get

$\lvert AO\rvert+\lvert BO\rvert-\lvert AB\rvert\geq\lvert AB\rvert/(8N^{4}).$

We can write a similarly inequality for $\lvert CO\rvert+\lvert
DO\rvert-\lvert CD\rvert$. Adding the two, we get

$\lvert AC\rvert+\lvert BD\rvert-\lvert AB\rvert-\lvert CD\rvert\geq(\lvert
AB\rvert+\lvert CD\rvert)/(8N^{4})\geq 2/(8N^{4}).$

The last inequality follows because distance between two integral points is at
least 1.

∎

###  3.1 Union of Near-Minimum Weight Perfect Matchings

In this subsection, we establish our main lemma that in a geometric bipartite
graph $G$, the union of near-minimum weight perfect matchings forms a planar
subgraph of $G$. This allows us to use the Tewari and Vinodchandran [TV12]
isolating weight scheme for planar bipartite graphs. We first define a near-
minimum weight perfect matching.

######  Definition 1.

Let the vertices of the geometric bipartite graph lie in the $N\times N$
integer grid. A perfect matching is said to be of near-minimum weight if its
weight is less than $w^{*}+1/(8N^{4})$, where $w^{*}$ is the minimum weight of
a perfect matching.

######  Lemma 2.

For a geometric bipartite graph $G$ with vertices in the $N\times N$ integer
grid, the union of near-minimum weight perfect matchings forms a planar graph.

###### Proof.

Let $A\cup B$ be the bipartition of the vertices. We will first show that no
two edges in a near-minimum weight perfect matching $M$ cross each other. For
the sake of contradiction, let there be two edges $\\{a_{1},b_{1}\\}$ and
$\\{a_{2},b_{2}\\}$ in $M$ that cross each other, where $a_{1},a_{2}\in A$ and
$b_{1},b_{2}\in B$. Since $G$ is a complete bipartite graph, every vertex of
set $A$ must have an edge to every vertex of set $B$ in $G$. We can construct
another matching $M^{\prime}$ from $M$ by replacing the crossing edges
$\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$ with $\\{a_{1},b_{2}\\}$ and
$\\{a_{2},b_{1}\\}$, respectively.

Note that $(a_{1},a_{2},b_{1},b_{2})$ form a convex quadrilateral, since its
diagonals $a_{1}b_{1}$ and $a_{2}b_{2}$ cross each other. From Lemma 1, we
know that

$\lvert a_{1}b_{2}\rvert+\lvert a_{2}b_{1}\rvert\leq\lvert
a_{1}b_{1}\rvert+\lvert a_{2}b_{2}\rvert-1/(4N^{4}).$

From here, we can conclude that $w(M^{\prime})\leq w(M)-1/(4N^{4})$, where
$w(M^{\prime})$ and $w(M)$ are the weights of $M^{\prime}$ and $M$,
respectively. This contradicts the fact that $M$ is a near-minimum weight
perfect matching.

Now, we will show that two edges belonging to two different near-minimum
weight perfect matchings cannot cross. Consider two such near-minimum weight
perfect matchings $M_{1}$ and $M_{2}$, where the edges $\\{a_{1},b_{1}\\}\in
M_{1}$ and $\\{a_{2},b_{2}\\}\in M_{2}$ cross each other. Observe that the
union of these two perfect matchings forms a set of vertex-disjoint cycles,
and a set of disjoint edges (which are common to both). There are two cases:
(i) the edges $\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$ are part of one of
these cycles and (ii) they are part of two different cycles. In each of the
cases, we will create two new perfect matchings with significantly smaller
weight, which will contradict the near-minimumness of $M_{1}$ and $M_{2}$.

Case (i): $\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$ are part of one cycle
$C$. See Figure 3. Note that the edges of this cycle come alternatingly from
$M_{1}$ and $M_{2}$ (shown in the figure in red and blue colors).

$a_{1}$$b_{1}$$a_{2}$$b_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$$C_{1}$$C_{2}$$C_{1}$$C_{2}$
Figure 3: Construction of $M^{\prime}_{1}$ and $M^{\prime}_{2}$, when the
crossing edges are part of one cycle
$a_{1}$$b_{1}$$a_{2}$$b_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$$C_{1}$$C_{2}$$C_{1}$$C_{2}$
Figure 4: Construction of $M^{\prime}_{1}$ and $M^{\prime}_{2}$, when the
crossing edges are part of two different cycles

We construct two distinct perfect matchings, $M_{1}^{\prime}$ and
$M_{2}^{\prime}$, using $M_{1}$ and $M_{2}$. Removing the edges
$\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$ from cycle $C$ divides it into two
parts. Note that both parts must have even number of edges, since the edges
are alternating between $M_{1}$ and $M_{2}$. It follows that one of these
parts is a path from $a_{1}$ to $a_{2}$, let us call it $C_{1}$. And the other
one is a path from $b_{1}$ to $b_{2}$, let us call it $C_{2}$ (as shown in
Figure 3).

Let us put $\\{a_{1},b_{2}\\}$ into $M_{1}^{\prime}$ and $\\{a_{2},b_{1}\\}$
into $M_{2}^{\prime}$. For the edges in $C_{1}$, we put the $M_{1}$ edges into
$M_{1}^{\prime}$ and the $M_{2}$ edges into $M_{2}^{\prime}$. For the edges in
$C_{2}$ we do the opposite, put the $M_{1}$ edges into $M_{2}^{\prime}$ and
the $M_{2}$ edges into $M_{1}^{\prime}$. For edges outside of the cycle $C$,
we put edges from $M_{1}$ into $M_{1}^{\prime}$ and edges from $M_{2}$ into
$M_{2}^{\prime}$.

Case (ii): $\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$ are part of two
different cycles. Let $C_{1}$ and $C_{2}$ be the paths obtained from removing
$\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$ from the two cycles, respectively.
See Figure 4. Here again we construct two distinct perfect matchings,
$M_{1}^{\prime}$ and $M_{2}^{\prime}$, using a similar uncrossing of edges.
Let us put both $\\{a_{1},b_{2}\\}$ and $\\{a_{2},b_{1}\\}$ into
$M_{1}^{\prime}$. For the edges in $C_{1}$, we put the $M_{1}$ edges into
$M_{1}^{\prime}$ and the $M_{2}$ edges into $M_{2}^{\prime}$. For the edges in
$C_{2}$ we do the opposite, put the $M_{1}$ edges into $M_{2}^{\prime}$ and
the $M_{2}$ edges into $M_{1}^{\prime}$. For edges outside the two cycles, we
put edges from $M_{1}$ into $M_{1}^{\prime}$ and edges from $M_{2}$ into
$M_{2}^{\prime}$.

Note that in both Case (i) and Case (ii), the newly constructed perfect
matchings $M_{1}^{\prime}$ and $M_{2}^{\prime}$ together have the same edges
as $M_{1}\cup M_{2}$, except for $\\{a_{1},b_{1}\\}$ and $\\{a_{2},b_{2}\\}$
being replaced with $\\{a_{2},b_{1}\\}$ and $\\{a_{1},b_{2}\\}$.

Let $w_{1},w_{2},w^{\prime}_{1},w^{\prime}_{2}$ be the weights of matchings
$M_{1},M_{2},M^{\prime}_{1},M_{2}^{\prime}$, repsectively. Then,

$w_{1}^{\prime}+w_{2}^{\prime}=w_{1}+w_{2}-\lvert a_{1}b_{1}\rvert-\lvert
a_{2}b_{2}\rvert+\lvert a_{1}b_{2}\rvert+\lvert a_{2}b_{1}\rvert.$

From Lemma 1, we have that

$\lvert a_{1}b_{1}\rvert+\lvert a_{2}b_{2}\rvert-\lvert
a_{1}b_{2}\rvert-\lvert a_{2}b_{1}\rvert\geq 1/(4N^{4}).$

Thus,

$w_{1}^{\prime}+w_{2}^{\prime}\leq w_{1}+w_{2}-1/(4N^{4}).$

Let $w^{*}$ be the weight of the minimum weight perfect matching. Since
$M_{1}$ and $M_{2}$ are of near-minimum weight, we have
$w_{1},w_{2}<w^{*}+1/(8N^{4})$. Using this with the above inequality, we get
$w^{\prime}_{1}+w^{\prime}_{2}<2w^{*}$. This implies that at least one of the
two matchings $M_{1}^{\prime}$ and $M_{2}^{\prime}$ have weight smaller than
$w^{*}$, which is a contradiction.

∎

###  3.2 Weight scheme

Now, we come to the design of an isolating weight assignment for the graph and
the proof of our main theorem. One of the components of our weight scheme is
the isolating weight assignment $W_{TV}$ constructed by Tewari and
Vinodchandran [TV12] for planar bipartite graph. We will use the same weight
scheme, but for any graph (not necessarily planar) embedded in the plane.

Consider a bipartite graph $G=(A,B,E)$ (not necessarily planar) with a
straight-line embedding in $\mathbb{R}^{2}$. For any vertex $u$, let
$(x_{u},y_{u})$ be the associated point in $\mathbb{R}^{2}$. For an edge
$e=(u,v)$, where $u\in A$ and $v\in B$, we define the weight function $W_{TV}$
as follows:

$W_{TV}(e)=(y_{v}-y_{u})\times(x_{v}+x_{u})$

Then, the theorem below says that $W_{TV}$ is isolating for bipartite planar
graphs.

######  Theorem 3 ([TV12]).

Let G be a planar bipartite graph. Then with respect to weight function
$W_{TV}$ (defined using any planar embedding), then the minimum weight perfect
matching in $G$, if one exists, is unique.

For a geometric bipartite graph, our main idea is to combine $W_{TV}$ with the
approximate distance function (up to a certain number of bits of precision)
The purpose of combining $W_{TV}$ is to break ties among minimum weight
perfect matchings according to the approximate distance function.

Let $G(A,B,E)$ be a geometric bipartite graph on the $N\times N$ integer grid.
Let $d(\cdot)$ be the weight function on the edges defined using the Euclidean
distance and let it naturally extend to subsets of edges. For any positive
integer $\ell$, let us define the approximate distance function
$d_{\ell}\colon E\to\mathbb{Z}$ as

$d_{\ell}(e)=\lfloor d(e)\times 2^{\ell}\rfloor.$

First let us show that the minimum weight perfect matchings with respect to
approximate distance function remain near-minimum with respect to the exact
distance function.

######  Claim 5.

For any positive integer $\ell$, let $M$ and $M^{*}$ be minimum weight perfect
matchings with respect to functions $d_{\ell}$ and $d$, respectively. Then,

$d(M)<d(M^{*})+n/2^{\ell}.$

###### Proof.

Observe that for any edge $e$, $2^{\ell}d(e)-1<d_{\ell}(e)\leq 2^{\ell}d(e)$.
Hence, for perfect matching $M$,

$2^{\ell}d(M)-n<d_{\ell}(M)\leq 2^{\ell}d(M).$

Then, we can write

$2^{\ell}d(M)<d_{\ell}(M)+n\leq d_{\ell}(M^{*})+n\leq 2^{\ell}d(M^{*})+n.$

This implies that $d(M)<d(M^{*})+n/2^{\ell}$. ∎

#### Weight scheme.

For any integer $\ell$, now let us define the combined weight function
$W_{\ell}$ on the edges as follows:

$W_{\ell}:=(2nN^{2}+1)\times d_{\ell}+W_{TV}$

Here, the scaling $d_{\ell}$ with a large number ensures that $W_{\ell}$ has
the same ordering of perfect matchings as $d_{\ell}$, and the $W_{TV}$
function plays the role of tie breaking. Our next lemma says that when to take
enough number of bits from the distance function and then combine it with
$W_{TV}$ as above, the resulting weight function is isolating.

######  Lemma 3.

For any integer $\ell\geq 4\log N+\log n+3$, the minimum weight perfect
matching in $G$ with respect to the weight function $W_{\ell}$ is unique.

###### Proof.

First observe that for any two perfect matchings $M_{1}$ and $M_{2}$,

$d_{\ell}(M_{1})>d_{\ell}(M_{2})\implies W_{\ell}(M_{1})>W_{\ell}(M_{2}).$

This is because the maximum contribution of $W_{TV}$ to the weight of a
matching can be at most $n\times 2N^{2}$. Thus, we can write

$\displaystyle W_{\ell}(M_{1})-W_{\ell}(M_{2})$
$\displaystyle=(2nN^{2}+1)(d_{\ell}(M_{1})-d_{\ell}(M_{2}))+W_{TV}(M_{1})-W_{TV}(M_{2})$
$\displaystyle\geq(2nN^{2}+1)\cdot 1+0-2nN^{2}.$ $\displaystyle\geq 1$

It follows that the set of minimum weight perfect matchings with respect to
$W_{\ell}$ is a subset of that with respect to $d_{\ell}$. Now, we argue that
these sets form a planar subgraph.

######  Claim 6.

The union of minimum weight perfect matchings with respect to $d_{\ell}$ forms
a planar subgraph.

###### Proof.

Let $M$ and $M^{*}$ be the minimum weight perfect matchings with respect to
functions $d_{\ell}$ and $d$, respectively. From Claim 5 we have that
$d(M)<d(M^{*})+n/2^{\ell}$. By substituting $\ell=4\log N+\log n+3$, we get
that the gap is less than $1/(8N^{4})$. Hence, $M$ is a near-minimum weight
perfect matching with respect to the $d(\cdot)$. Then, the claim follows from
Lemma 2. ∎

To finish the proof of the lemma, let $H$ be the subgraph formed by the union
of minimum weight perfect matchings with respect to $d_{\ell}$. Clearly,
$d_{\ell}$ gives equal weights to all the perfect matchings in $H$. Thus, the
function $W_{\ell}$ is same as $W_{TV}$ on $H$ (up to an additive constant).
From Theorem 3, we know that $W_{TV}$ ensures a unique minimum weight perfect
matching in the planar graph $H$. Hence, so does $W_{\ell}$. ∎

#### Proof of the main theorem (Theorem 2)

Once we have shown how to construct an isolating weight assignment, we just
need to use the algorithm of Mulmuley, Vazirani and Vazirani [MVV87] to
construct the minimum weight perfect matching.

######  Theorem 4 ([MVV87]).

Given a graph $G=(V,E)$ with an isolating weight assignment on the edges that
uses $O(\log n)$ bits, there is an NC algorithm to find the minimum-weight
perfect matching.

Now, we are ready to prove the main theorem. Suppose we are given a bipartite
set of $2n$ points in $N\times N$ integer grid. Recall that the weight of an
edge is defined to be the Euclidean distance between the endpoints. Our goal
is to construct a perfect matching whose weight is at most $w^{*}+\delta$,
where $\delta$ is the given error parameter and $w^{*}$ is the minimum weight
of a perfect matching. If we choose $\ell\geq\log(n/\delta)$, then from Claim
5, we know that a minimum weight perfect matching with respect to function
$d_{\ell}(\cdot)$ will have the desired property.

We choose $\ell=\max\\{\log(n/\delta),4\log N+\log n+3\\}$. Then we use the
weight scheme $W_{\ell}$ with the MVV algorithm (Theorem 4). Recall that from
Lemma 3, we have the isolation property required in Theorem 4. Finally, let us
analyse the number of bits used by weight function $W_{\ell}$. The maximum
weight given to any edge by function $d(\cdot)$ is at most $\sqrt{2}N$ and by
function $W_{TV}$, it is at most $2N^{2}$. Thus, maximum weight given to any
edge by function $W_{\ell}$ will be at most
$2^{\ell}\times\sqrt{2}N\times(2nN^{2}+1)+2N^{2}$. The number of bits in
weight of any edge come out to be $O(\log Nn/\delta)$. Hence, we have an NC
algorithm, whenever $N$ and $1/\delta$ are polynomial in $n$.

##  4 Conclusion

In this work, we explored the parallel complexity of EWPM problem. We
established a lower bound which shows that for EWPM, a linear number of bits
is required to distinguish the minimum-weight perfect matching from others.
Next, we showed that EWPM problem that allows up to
$\frac{1}{\operatorname{poly}(n)}$ error, is in NC. The main question arises
from our work is whether the non-bipartite version of EWPM is also in NC.
Another possible extension is to consider the bipartite version in 3 or higher
dimensions.

## References

  * [ACRX22] Pankaj K Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao.  Deterministic, near-linear $\varepsilon$-approximation algorithm for geometric bipartite matching.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1052–1065, 2022.
  * [ACX19] Pankaj K Agarwal, Hsien-Chih Chang, and Allen Xiao.  Efficient algorithms for geometric partial matching.  In 35th International Symposium on Computational Geometry (SoCG 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [AES95] Pankaj K Agarwal, Alon Efrat, and Micha Sharir.  Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications.  In Proceedings of the eleventh annual symposium on Computational geometry, pages 39–50, 1995.
  * [AV20] Nima Anari and Vijay V. Vazirani.  Planar graph perfect matching is in NC.  J. ACM, 67(4):21:1–21:34, 2020.
  * [CL10] Qi Cheng and Yu-Hsin Li.  Finding the smallest gap between sums of square roots.  In Alejandro López-Ortiz, editor, LATIN 2010: Theoretical Informatics, pages 446–455, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  * [CO07] Richard Carr and Cormac O’Sullivan.  On the linear independence of roots.  International Journal of Number Theory, 05:161–171, 2007.
  * [DK98] Elias Dahlhaus and Marek Karpinski.  Matching and multidimensional matching in chordal and strongly chordal graphs.  Discrete Applied Mathematics, 84(1-3):79–91, 1998.
  * [DKR10] Samir Datta, Raghav Kulkarni, and Sambuddha Roy.  Deterministically isolating a perfect matching in bipartite planar graphs.  Theory of Computing Systems, 47(3):737–757, 2010.
  * [Edm65] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of mathematics, 17:449–467, 1965.
  * [EHS23] Friedrich Eisenbrand, Matthieu Haeberle, and Neta Singer.  An improved bound on sums of square roots via the subspace theorem.  CoRR, abs/2312.02057, 2023.  To appear in SoCG 2024.  arXiv:2312.02057.
  * [FGT16] Stephen Fenner, Rohit Gurjar, and Thomas Thierauf.  Bipartite perfect matching is in quasi-NC.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 754–763, 2016.
  * [GK87] Dima Yu Grigoriev and Marek Karpinski.  The matching problem for bipartite graphs with polynomially bounded permanents is in NC.  In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 166–172. IEEE, 1987.
  * [GPST92] Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, and Éva Tardos.  Using interior-point methods for fast parallel algorithms for bipartite matching and related problems.  SIAM J. Comput., 21(1):140–150, feb 1992.
  * [HK73] John E Hopcroft and Richard M Karp.  An n^5/2 algorithm for maximum matchings in bipartite graphs.  SIAM Journal on computing, 2(4):225–231, 1973.
  * [KUW85] Richard M Karp, Eli Upfal, and Avi Wigderson.  Constructing a perfect matching is in random NC.  In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 22–32, 1985.
  * [Lov79] László Lovász.  On determinants, matchings, and random algorithms.  In FCT, volume 79, pages 565–574, 1979.
  * [Mad13] Aleksander Madry.  Navigating central path with electrical flows: From flows to matchings, and back.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 253–262. IEEE, 2013.
  * [MVV87] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani.  Matching is as easy as matrix inversion.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 345–354, 1987.
  * [O’R81] Joseph O’Rourke.  Advanced problem 6369.  Amer. Math. Monthly, 88(10):769, 1981.
  * [PS98] Christos H Papadimitriou and Kenneth Steiglitz.  Combinatorial optimization: algorithms and complexity.  Courier Corporation, 1998.
  * [SA12] R Sharathkumar and Pankaj K Agarwal.  Algorithms for the transportation problem in geometric settings.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 306–317. SIAM, 2012.
  * [Sha13] R Sharathkumar.  A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates.  In Proceedings of the twenty-ninth annual symposium on Computational geometry, pages 9–16, 2013.
  * [ST17] Ola Svensson and Jakub Tarnawski.  The matching problem in general graphs is in quasi-NC.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 696–707. Ieee, 2017.
  * [TOP] The open problems project: problem 33 sum of square roots.  https://topp.openproblem.net/p33.  Accessed: 2010-09-30.
  * [TV12] Raghunath Tewari and NV Vinodchandran.  Green’s theorem and isolation in planar graphs.  Information and Computation, 215:1–7, 2012.
  * [VA99] Kasturi R Varadarajan and Pankaj K Agarwal.  Approximation algorithms for bipartite and non-bipartite matching in the plane.  In SODA, volume 99, pages 805–814, 1999.
  * [Var98] Kasturi R Varadarajan.  A divide-and-conquer algorithm for min-cost perfect matching in the plane.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 320–329. IEEE, 1998.
  * [VDBCP+23] Jan Van Den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford.  A deterministic almost-linear time algorithm for minimum-cost flow.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 503–514. IEEE, 2023.
  * [vdBLN+20] Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.  Bipartite matching in nearly-linear time on moderately dense graphs.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 919–930. IEEE, 2020.