Matching under Metric Privacy

We study minimum-total-distance matching between public and private points under local metric privacy. We compare perturbing original points, distance vectors, and a projected representation that preserves distances to the public candidates. We then correct the projected representation using one additional private distance. Its expected additional matching cost is $O(n\sqrt{m\log (2n)}/\epsilon )$, where $m\le \min \{n,d\}$, without distributional or boundedness assumptions on the private points. The correction controls errors in relative costs rather than individual locations. Two constructions reverse the ranking of projected and distance-vector reports, showing why reconstruction error alone does not explain matching quality. Synthetic experiments examine these comparisons and the tradeoff between public approximation and privacy noise.