Math @ Duke

Publications [#235415] of Pankaj K. Agarwal
Papers Published
 Varadarajan, KR; Agarwal, PK, Approximation algorithms for bipartite and nonbipartite matching in the plane,
in Tenth Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1999),
pp. 805814
(last updated on 2018/02/21)
Abstract: In the approximate Euclidean mincost perfect matching problem, we are a given a set V of 2n points in the plane, and a real number ε<0, and we want to pair up the points (into n pairs) so that the sum of the distances between the paired points is within a multiplicative factor of (1+ε) of the optimal. We present a MonteCarlo algorithm that returns, with probability at least 1/2, a solution within (1+ε) of the optimal; the running time of our algorithm is O((n/ε3) log6 n). In the bipartite version of this problem, we are given a set R of n red points, a set B of n blue points in the plane, and a real number ε>0. We want to match each red point with a blue point so that the sum of the distances between paired points is within (1+ε) times that of an optimal matching. We present an algorithm for this problem that runs in O((n/ε)3/2 log5 n) time.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

