Deterministic, near-linear 𝜀 -approximation algorithm for geometric bipartite matching

Abstract: Given point sets

A

and

B

in

m a t h b b R^{d}

where

A

and

B

have equal size

n

for some constant dimension

d

and a parameter

v a r e p s i l o n > 0

, we present the first deterministic algorithm that computes, in

n c d o t (v a r e p s i l o n^{- 1} l o g n)^{O (d)}

time, a perfect matching between

A

and

B

whose cost is within a

(1 + v a r e p s i l o n)

factor of the optimal under any

s m a s h e l l_{p}

-norm. Although a Monte-Carlo algorithm with a similar running time is proposed by Raghvendra and Agarwal [J. ACM 2020], the best-known deterministic

v a r e p s i l o n

-approximation algorithm takes

O m e g a (n^{3 / 2})

time. Our algorithm constructs a (refinement of a) tree cover of

m a t h b b R^{d}

, and we develop several new tools to apply a tree-cover based approach to compute an

v a r e p s i l o n

-approximate perfect matching.

Cited in

(14)

This page was built for publication: Deterministic, near-linear 𝜀 -approximation algorithm for geometric bipartite matching