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 ) B log 2 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 ) n log n -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.

Authors

• Shinwoo An
• Eunjin Oh 0001
• Jie Xue 0003

Keywords

• Euclidean matching problem
• many-to-many matching
• multimatching
• the edge cover problem