Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

A Faster Maximum Cardinality Matching Algorithm with Applications in Machine Learning

Nathaniel Lahn · Sharath Raghvendra · Jiacheng Ye

Keywords: [ Machine Learning ] [ Optimization ] [ Graph Learning ]


Abstract: Maximum cardinality bipartite matching is an important graph optimization problem with several applications. For instance, maximum cardinality matching in a δ-disc graph can be used in the computation of the bottleneck matching as well as the -Wasserstein and the Lévy-Prokhorov distances between probability distributions. For any point sets A,BR2, the δ-disc graph is a bipartite graph formed by connecting every pair of points (a,b)A×B by an edge if the Euclidean distance between them is at most δ. Using the classical Hopcroft-Karp algorithm, a maximum-cardinality matching on any δ-disc graph can be found in ˜O(n3/2) time.~\footnote{We use ˜O() to suppress poly-logarithmic terms in the complexity.} In this paper, we present a simplification of a recent algorithm (Lahn and Raghvendra, JoCG 2021) for the maximum cardinality matching problem and describe how a maximum cardinality matching in a δ-disc graph can be computed asymptotically faster than O(n3/2) time for any moderately dense point set. As applications, we show that if A and B are point sets drawn uniformly at random from a unit square, an exact bottleneck matching can be computed in ˜O(n4/3) time. On the other hand, experiments suggest that the Hopcroft-Karp algorithm seems to take roughly Θ(n3/2) time for this case. This translates to substantial improvements in execution time for larger inputs.

Chat is not available.