Approximation Algorithms for Bipartite Matching with Metric and Geometric Costs

Let G = G(AUB,A x B), with vertical bar A vertical bar =vertical bar B vertical bar = n, be a weighted bipartite graph, and let d(.,.) be the cost function on the edges. Let w(M) denote the weight of a matching in G, and M* a minimum-cost perfect matching in G. We call a perfect matching M c-approximate, for c >= 1, if w(M) <= c . w(M*). We present three approximation algorithms for computing minimum-cost perfect matchings in G. First, we consider the case when d(.,.) is a metric. For any delta > 0, we present an algorithm that, in O(n(2+delta) log n log(2) (1/delta)) time, computes a O(1/delta(alpha))-approximate matching of G, where alpha = log(3) 2 approximate to 0.631. Next, we assume the existence of a dynamic data structure for answering approximate nearest neighbor (ANN) queries under d(.,.). Given two parameters epsilon, delta is an element of (0, 1), we present an algorithm that, in O(epsilon(-2) n(1+delta)tau (n, epsilon) log(2) (n/epsilon) log(1/delta)) time, computes a O(1/delta(alpha))-approximate matching of G, where alpha = 1 + log(2)(1 + epsilon) and tau (n, epsilon) is the query and update time of an (epsilon/2)-ANN data structure. Finally, we present an algorithm that works even if d(.,.) is not a metric but admits an ANN data structure for d(.,.). In particular, we present an algorithm that computes, in O(epsilon(-1)n(3/2)tau(n, epsilon) log(4) (n/epsilon) E) log Delta) time, a (1 + epsilon)-approximate matching of A and B; here Delta is the ratio of the largest to the smallest-cost edge in G, and tau(n, epsilon) is the query and update time of an (epsilon/c)-ANN data structure for some constant c > 1. We show that our results lead to faster matching algorithms for many geometric settings.