A near-linear constant-factor approximation for euclidean bipartite matching?

ABSTRACT

In the Euclidean bipartite matching problem, we are given a set R of "red" points and a set B of "blue" points in ℝ³ 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.

REFERENCES

• 1: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.39-50, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220284]
• 2: Kasturi R. Varadarajan , Pankaj K. Agarwal, Approximation algorithms for bipartite and non-bipartite matching in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.805-814, January 17-19, 1999, Baltimore, Maryland, United States
• 3: S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.554, October 19-22, 1997
• 4: D. S. Atkinson and P. M. Vaidya. Using geometry to solve the transportation problem in the plane. Algorithmica, 13:442--461, 1995.
• 5: Paul B. Callahan , S. Rao Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.291-300, January 25-27, 1993, Austin, Texas, United States
• 6: J. Edmonds. Maximum matching and a polyhedron with (0,1) vertices. J. Res. National Bureau of Standards, 69B:125--130, 1965.
• 7: H. N. Gabow , R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, v.18 n.5, p.1013-1036, Oct. 1989 [doi>10.1137/0218069]
• 8: Z. Galil, S. Micali, and H. N. Gabow. Priority queues with variable priority and an o(ev log v) algorithm for finding a maximal weighted matching in general graphs. In Proc. 22nd Annual IEEE Symposium on Foundations of Computer Science, pages 255--261, 1982.
• 9: H. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist. Q., 2:83--97, 1955.
• 10: E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart & Winston, New York, 1976.
• 11: S. B. Rao and W. D. Smith. Improved approximation schemes for traveling salesman tours. In Proc. 30th Annu. ACM Sympos. Theory Comput., 1998.
• 12: P. M. Vaidya. Approximate minimum weight matching on points in k-dimensional space. Algorithmica, 4:569-583, 1989.
• 13: P. M. Vaidya, Geometry helps in matching, SIAM Journal on Computing, v.18 n.6, p.1201-1225, Dec. 1989 [doi>10.1137/0218080]
• 14: Kasturi R. Varadarajan, A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.320, November 08-11, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Theory

Keywords:
approximation algorithms, combinatorial optimization, matching