Approximation algorithms for bipartite and non-bipartite matching in the plane

No abstract is available for this paper.

• Publication year

  1999

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A divide-and-conquer algorithm for min-cost perfect matching in the plane

  1998influential reference
• Nearly linear time approximation schemes for Euclidean TSP and other geometric problems

  1997influential reference
• Improvements on bottleneck matching and related problems using geometry

  1996cited by this paper
• Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications

  1995cited by this paper
• Clique partitions, graph compression and speeding-up algorithms

  1991cited by this paper
• Faster Scaling Algorithms for Network Problems

  1989influential reference
• Geometry helps in matching

  1989influential reference
• An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

  1986cited by this paper
• A survey of heuristics for the weighted matching problem

  1983cited by this paper
• Maximum matching and a polyhedron with 0,1-vertices

  1965cited by this paper

• Algorithms for Computing Chromatic Polynomials and Chromatic Index Polynomials

  2024cites this paper
• An O(n log n)-Time Approximation Scheme for Geometric Many-to-Many Matching

  2024influential citation
• Geometric Bipartite Matching is in NC

  2024cites this paper
• Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching

  2024cites this paper
• Parallel Complexity of Geometric Bipartite Matching

  2024cites this paper
• A Data-dependent Approach for High-dimensional (Robust) Wasserstein Alignment

  2022cites this paper
• Deterministic, near-linear 𝜀-approximation algorithm for geometric bipartite matching

  2022cites this paper
• Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane

  2021cites this paper
• A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching

  2020influential citation
• Geometric Optimization Revisited

  2019cites this paper
• Faster Algorithms for the Geometric Transportation Problem

  2019cites this paper
• Approximate Minimum-Weight Matching with Outliers under Translation

  2018cites this paper
• Preserving Privacy with Probabilistic Indistinguishability in Weighted Social Networks

  2017cites this paper
• Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost

  2016cites this paper
• A decentralized geometric approach for the formation keeping in unmanned aircraft navigation

  2015cites this paper
• Improved algorithm for weighted matching of employees

  2015cites this paper
• Improved algorithm for weighted matching of employees by Emil Olofsson

  2015cites this paper
• Linear-Time Approximation for Maximum Weight Matching

  2014cites this paper
• Approximation algorithms for bipartite matching with metric and geometric costs

  2014influential citation
• A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates

  2013influential citation
• Ugur Kirbac Image Labeling and Classification by Semantic Tag Analy

  2013cites this paper
• Parallel algorithms for geometric graph problems

  2013cites this paper
• Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance

  2012cites this paper
• A near-linear time ε-approximation algorithm for geometric bipartite matching

  2012influential citation
• Algorithms for the transportation problem in geometric settings

  2012cites this paper
• Algorithms and lower bounds in the streaming and sparse recovery models

  2012cites this paper
• A Randomized Fully Polynomial-time Approximation Scheme for Weighted Perfect Matching in the Plane

  2012influential citation
• Є-Samples for Kernels

  2011cites this paper
• Photo Retrieval Based on Spatial Layout with Hardware Acceleration for Mobile Devices

  2011cites this paper
• Scaling algorithms for approximate and exact maximum weight matching

  2011cites this paper
• A Near-Linear Time ε-Approximation Algorithm for Bipartite Geometric Matching

  2011cites this paper
• K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

  2011cites this paper
• Batch testing, adaptive algorithms, and heuristic applications for stable marriage problems

  2010cites this paper
• On constant factor approximation for earth mover distance over doubling metrics

  2010cites this paper
• Distance-based analysis of dynamical systems and time series by optimal transport

  2010cites this paper
• Sparse recovery for Earth Mover Distance

  2010cites this paper
• Aggregation error for location models: survey and analysis

  2009cites this paper
• On Channel-Discontinuity-Constraint Routing in Wireless Networks

  2009cites this paper
• Photo retrieval based on spatial layout with hardware acceleration

  2009cites this paper
• Efficient Sketches for Earth-Mover Distance, with Applications

  2009cites this paper
• Efficient Sketches for EarthMover Distance , with Applications

  2009cites this paper
• Efficient sketches for EarthMover Distance , with applications ∗

  2009cites this paper
• A Survey on Algorithms for Euclidean Matching

  2008cites this paper
• Approximation schemes for geometric problems

  2007cites this paper
• A near linear time constant factor approximation for Euclidean bichromatic matching (cost)

  2007cites this paper
• An Approximate Graph Matching Technique for Integrity Monitoring in Integrated Intelligent Flight Deck Applications

  2006cites this paper
• Integrity Monitoring of Digital Elevation Models using Corner Edge Detection of Accumulated X-Band Radials

  2006cites this paper
• Distributed Coordination Collecting, Locking, and Matching

  2006cites this paper
• Gestalt-based feature similarity measure in trademark database

  2006cites this paper
• On Bipartite Matching under the RMS Distance

  2006influential citation
• Fast Algorithms for Weighted Bipartite Matching

  2005cites this paper
• Exact and approximate graph matching using random walks

  2005cites this paper
• Matching point sets with respect to the Earth mover's distance

  2005influential citation
• A near-linear constant-factor approximation for euclidean bipartite matching?

  2004cites this paper
• Fast and Simple Algorithms for Weighted Perfect Matching

  2004cites this paper
• Algorithms for planar graphs

  2003cites this paper
• Fast Clustering and Minimum Weight Matching Algorithms for Very Large Mobile Backbone Wireless Networks

  2003cites this paper
• Energy Optimal Routing in Radio Networks Using Geometric Data Structures

  2002cites this paper
• ITR/ACS+IM Computational Geometry for Structural Biology and Bioinformatics

  2002cites this paper
• Randomized Algorithms for Geometric Optimization Problems

  2001cites this paper
• Geometric matching of weighted point sets

  2000cites this paper