Math @ Duke

Publications [#235550] of Pankaj K. Agarwal
Papers Published
 Sharathkumar, R; Agarwal, PK, A nearlinear time εapproximation algorithm for geometric bipartite matching,
Proceedings of the Annual Acm Symposium on Theory of Computing
(June, 2012),
pp. 385394, ISSN 07378017 [doi]
(last updated on 2018/11/15)
Abstract: For point sets A,B ⊂ ℝd, A=B=n, and for a parameter ε > 0, we present an algorithm that computes, in O(n poly(log n, 1/ε)) time, an εapproximate perfect matching of A and B with high probability; the previously best known algorithm takes Ω(n3/2) time. We approximate the Lpnorm using a distance function, d(·,·) based on a randomly shifted quadtree. The algorithm iteratively generates an approximate minimumcost augmenting path under d(·,·) in time proportional to the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O((n/ε)log n), implying that the running time of our algorithm is O(n poly(log n,1/ε)). © 2012 ACM.


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

