A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching

DOI10.1145/3393694MaRDI QIDQ5133973zbMATH OpenOpenAlexFDO

Authors Sharath Raghvendra, Pankaj K. Agarwal

Publication date 11 November 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.406.7261

zbMATH Keywords

approximation algorithmsbipartite matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• A near-linear time ε-approximation algorithm for geometric bipartite matching
• Deterministic, near-linear 𝜀 -approximation algorithm for geometric bipartite matching
• Approximation algorithms for bipartite matching with metric and geometric costs
• scientific article; zbMATH DE number 1305475
• A near-linear constant-factor approximation for Euclidean bipartite matching?
• scientific article; zbMATH DE number 6381629
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
• A randomized O(^2k)-competitive algorithm for metric bipartite matching

Cited in

(11)

• scientific article; zbMATH DE number 6381629 (Why is no real title available?)
• scientific article; zbMATH DE number 1305475 (Why is no real title available?)
• Efficient algorithms for geometric partial matching
• A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates
• Approximation algorithms for bipartite matching with metric and geometric costs
• A near-linear constant-factor approximation for Euclidean bipartite matching?
• Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b–Matching Problems in Nonbipartite Graphs
• A near-linear time ε-approximation algorithm for geometric bipartite matching
• Dynamic Euclidean bottleneck matching
• An o(n n)-time approximation scheme for geometric many-to-many matching
• An 0(n log n) algorithm for the convex bipartite matching problem

This page was built for publication: A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5133973)