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 α = log 3 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 ε, &delta ∈ (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 + log 2 (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.

Authors

• Pankaj K. Agarwal
• Sharath Raghvendra

Keywords

• approximation algorithms
• matching