Approximation Algorithms for the Geometric Multimatching Problem

Let S and T be two point sets in a metric space (M,d) with |S|+|T|=n, and b:S∪ T→ ℕ be a function satisfying b(s)≤ |T| for s∈ S and b(t)≤ |S| for t∈ T. We call a function µ:S× T→ 0,1 a multimatching between S and T with respect to b if for each s∈ S (and t∈ T), the number of points t∈ T (and s∈ S) with µ(s,t)=1 is at least b(s) (and b(t)). The cost of a multimatching µ is defined as cost(µ)=∑(s,t)µ(s,t)· d(s,t) where d(s,t) is the distance between s and t in M. The geometric multimatching problem aims to find a multimatching that minimizes its cost. The special case that b(v)=1 for all v∈ S∪ T is known as the geometric many-to-many matching problem. We present two results for the geometric multimatching problem and the geometric many-to-many matching problem when a metric space M has a doubling dimension ddim. Notably, we present the first near-linear-time approximation scheme for the geometric multimatching problem with respect to the output size. Furthermore, our second result improves the best-known (1+ε)-approximation algorithm for the geometric many-to-many matching problem presented by Bandyapadhyay and Xue [SoCG24], winning the best paper award at SoCG’24. More specifically, we present the following two algorithms: 1. A (1/ε)O(ddim) Blog2 n-time deterministic algorithm that returns a multimatching of cost at most (1+ε) times the cost of an optimal multimatching for any constant ε>0, where B denotes the summation of b(v) for all v∈ S∪ T. 2. A (1/ε)O(ddim) nlogn-time deterministic algorithm that returns a many-to-many matching of cost at most (1+ε) times the cost of an optimal many-to-many matching for any constant ε>0.