Approximation algorithms for bipartite matching with metric and geometric costs

Let G = G(A ∪ B, A×B), with |A | = |B | = 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 δ> 0, we present an algorithm that, in O(n 2+δ log n log 2 (1/δ)) time, computes a O(1/δ α)-approximate matching of G, where α = log3 2 ≈ 0.631. Next, we assume the existence of a dynamic data structure for answering approximate nearest neighbor (ANN) queries under d(·, ·). Given two parameters ε, δ ∈ (0, 1), we present an algorithm that, in O(ε −2 n 1+δ τ(n, ε) log 2 (n/ε) log(1/δ)) time, computes a O(1/δ α)-approximate matching of G, where α = 1 + log2(1 + ε) and τ(n, ε) is the query and update time of an (ε/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(ε −1 n 3/2 τ(n, ε) log 4 (n/ε) log ∆) time, a (1 + ε)approximate matching of A and B; here ∆ is the ratio of the largest to the smallest-cost edge in G, and τ(n, ε) is the query and update time of an (ε/c)-ANN data structure for some constant c> 1. We show that our results lead to faster matching algorithms for many geometric settings.