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,B⊂R2, 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.