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

Math @ Duke





.......................

.......................


Publications [#235415] of Pankaj K. Agarwal

Papers Published

  1. Varadarajan, KR; Agarwal, PK, Approximation algorithms for bipartite and non-bipartite matching in the plane, in Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1999), pp. 805-814
    (last updated on 2017/12/12)

    Abstract:
    In the approximate Euclidean min-cost 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 Monte-Carlo 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 27708-0320