Bandyapadhyay, Sayan ;
Maheshwari, Anil ;
Smid, Michiel
Exact and Approximation Algorithms for ManyToMany Point Matching in the Plane
Abstract
Given two sets S and T of points in the plane, of total size n, a manytomany 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 minimumcost manytomany matching problem, the goal is to compute a manytomany matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimumweight 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 [Justin Colannino et al., 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(n^{3/2}⋅ poly(log n)) time (1+ε)approximation in the planar case.
BibTeX  Entry
@InProceedings{bandyapadhyay_et_al:LIPIcs.ISAAC.2021.44,
author = {Bandyapadhyay, Sayan and Maheshwari, Anil and Smid, Michiel},
title = {{Exact and Approximation Algorithms for ManyToMany Point Matching in the Plane}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {44:144:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15477},
URN = {urn:nbn:de:0030drops154779},
doi = {10.4230/LIPIcs.ISAAC.2021.44},
annote = {Keywords: Manytomany matching, bipartite, planar, geometric, approximation}
}
30.11.2021
Keywords: 

Manytomany matching, bipartite, planar, geometric, approximation 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 