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

Conference Paper

Given two point sets A and B in g.,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 logn)O(d) time, a perfect matching between A and B whose cost is within a (1+ϵ) factor of the optimal matching under any g.,"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 ω(n3/2) time. Our algorithm constructs a (refinement of a) tree cover of g.,d, and we develop several new tools to apply a tree-cover based approach to compute an ϵ-approximate perfect matching.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Chang, HC; Raghvendra, S; Xiao, A

### Published Date

- September 6, 2022

### Published In

### Start / End Page

- 1052 - 1065

### International Standard Serial Number (ISSN)

- 0737-8017

### International Standard Book Number 13 (ISBN-13)

- 9781450392648

### Digital Object Identifier (DOI)

- 10.1145/3519935.3519977

### Citation Source

- Scopus