Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235351] of Pankaj K. Agarwal

Papers Published

  1. 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. 555-564, ISSN 0737-8017 [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 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 ε,δ∈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 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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320