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 , the -disc graph is a bipartite graph formed by connecting every pair of points 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 time.~\footnote{We use 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 time for any moderately dense point set. As applications, we show that if and are point sets drawn uniformly at random from a unit square, an exact bottleneck matching can be computed in time. On the other hand, experiments suggest that the Hopcroft-Karp algorithm seems to take roughly time for this case. This translates to substantial improvements in execution time for larger inputs.
Chat is not available.