Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235461] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Varadarajan, KR, A near-linear constant-factor approximation for euclidean bipartite matching?, Proceedings of the Annual Symposium on Computational Geometry (2004), pp. 247-252
    (last updated on 2018/12/09)

    In the Euclidean bipartite matching problem, we are given a set R of "red" points and a set B of "blue" points in ℝ d where |R|= |B| = n, and we want to pair up each red point with a distinct blue point so that the sum of distances between the paired points is minimized. We present an approximation algorithm that given any parameter 0 < ε < 1 runs in O(n 1+ε) expected time and returns a matching whose expected cost is within a multiplicative factor O(log(1/ε)) of the optimal. The dimension d is considered to be a fixed constant.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320