Approximation algorithms for bipartite matching with metric and geometric costs

Journal Article

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 log n log (1/δ)) time, computes a O(1/δ )-approximate matching of G, where α = log 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 ε,δ∈2 (0, 1), we present an algorithm that, in O(ε n τ (n, ε) log (n/ε) log(1/δ)) time, computes a O(1/δ )- approximate matching of G, where α = 1 + log (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(ε n τ (n, ε) log (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. 2+δ 2 α -2 1+δ 2 α -1 3/2 4 3 2

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sharathkumar, R

Published Date

  • January 1, 2014

Published In

Start / End Page

  • 555 - 564

International Standard Serial Number (ISSN)

  • 0737-8017

Digital Object Identifier (DOI)

  • 10.1145/2591796.2591844

Citation Source

  • Scopus