# An Improved ϵ-Approximation Algorithm for Geometric Bipartite Matching

Conference Paper

For two point sets A,B ⊂ Rd, with |A| = |B| = n and d > 1 a constant, and for a parameter ϵ> 0, we present a randomized algorithm that, with probability at least 1/2, computes in O(n(ϵ-O(d3) log log n + ϵ-O(d) log4 n log5 log n)) time, an ϵ-approximate minimum-cost perfect matching under any Lp-metric. All previous algorithms take n(ϵ-1 log n)ω(d) time. We use a randomly-shifted tree, with a polynomial branching factor and O(log log n) height, to define a tree-based distance function that ϵ-approximates the Lp metric as well as to compute the matching hierarchically. Then, we apply the primal-dual framework on a compressed representation of the residual graph to obtain an efficient implementation of the Hungarian-search and augment operations.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Raghvendra, S; Shirzadian, P; Sowle, R

### Published Date

- June 1, 2022

### Published In

### Volume / Issue

- 227 /

### International Standard Serial Number (ISSN)

- 1868-8969

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

- 9783959772365

### Digital Object Identifier (DOI)

- 10.4230/LIPIcs.SWAT.2022.6

### Citation Source

- Scopus