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

Given two point sets A and B in ℝ d of size n each, for some constant dimension d ≥ 1, and a parameter ε>0, we present a deterministic algorithm that computes, in n ·(ε −1 log n ) O ( d ) time, a perfect matching between A and B whose cost is within a (1+ε) factor of the optimal matching under any ℓ 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 ε-approximation algorithm takes Ω( n 3/2 ) time. Our algorithm constructs a (refinement of a) tree cover of ℝ d , and we develop several new tools to apply a tree-cover based approach to compute an ε-approximate perfect matching.

Authors

• Pankaj K. Agarwal
• Hsien-Chih Chang
• Sharath Raghvendra
• Allen Xiao

Keywords

• augmenting path
• compression
• matching
• regularizer
• tree cover