Answers are grounded in this paper and cite their sources.
Given two sets S and T of points in the plane, of total size n, a {many-to-many} matching between S and T is a set of pairs $(p,q)$ such that p∈ S, q∈ T and for each r∈ S∪ T, r appears in at least one such pair. The {cost of a pair} $(p,q)$ is the (Euclidean) distance between p and q. In the {minimum-cost many-to-many matching} problem, the goal is to compute a many-to-many matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimum-weight edge cover in a bipartite graph, and hence can be solved in O(n³) time. In a more restricted setting where all the points are on a line, the problem can be solved in O(nlog n) time [Colannino, Damian, Hurtado, Langerman, Meijer, Ramaswami, Souvaine, Toussaint; Graphs Comb., 2007]. However, no progress has been made in the general planar case in improving the cubic time bound. In this paper, we obtain an O(n²· poly(log n)) time exact algorithm and an O( n3/2· poly(log n)) time $(1+ε)$-approximation in the planar case. Our results affirmatively address an open problem posed in [Colannino et al., Graphs Comb., 2007].
No takes yet. Share an insight, caveat, or question.
Bandyapadhyay et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: