Math @ Duke

Publications [#235351] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharathkumar, R, Approximation algorithms for bipartite matching with metric and geometric costs,
Proceedings of the Annual ACM Symposium on Theory of Computing
(January, 2014),
pp. 555564, ISSN 07378017 [doi]
(last updated on 2017/12/17)
Abstract: 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 minimumcost perfect matching in G. We call a perfect matching M capproximate, for c ≥1, if w(M)≤ c·w(M*). We present three approximation algorithms for computing minimumcost 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 ε,δ∈2 (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 smallestcost 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

