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(n2+δ log n log2(1/δ)) time, computes a O(1/δα)-approximate matching of G, where α = log32 ≈ 0:631. Next, we assume the existence of a dynamic data structure for answering approximate nearest neighbor (ANN) queries under d(·, ·). Given two parameters ε,δ∈2 (0, 1), we present an algorithm that, in O(ε-2n1+δτ (n, ε) log2(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(ε-1n3/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. © 2014 ACM.
Agarwal, PK; Sharathkumar, R
Start / End Page
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)