A near-linear time ε-approximation algorithm for geometric bipartite matching

DOI10.1145/2213977.2214014zbMath1286.05140OpenAlexW2047239272MaRDI QIDQ5415489

R. Sharathkumar, Pankaj K. Agarwal

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2213977.2214014

zbMATH Keywords

matchingapproximation algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (10)

Linear-Time Approximation for Maximum Weight Matching ⋮ Unnamed Item ⋮ Improved PTASs for convex barrier coverage ⋮ On Geometric Prototype and Applications ⋮ Preconditioning for the Geometric Transportation Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Maximum bipartite matchings with low rank data: locality and perturbation analysis ⋮ A unified framework for clustering constrained data without locality property

This page was built for publication: A near-linear time ε-approximation algorithm for geometric bipartite matching