The minimum-cost bipartite matching problem between two point sets R and S in a metric space has numerous applications in machine learning, computer vision, and logistics. For example, it arises in estimating the 1-Wasserstein distance between continuous probability distributions, as well as in efficiently assigning taxi requests to customers while minimizing travel cost prior to pickup. However, computing a minimum-cost matching in general metric spaces is computationally demanding. This challenge is particularly acute in dynamic settings where points arrive over time and each update would naively require recomputing the solution from scratch.In this work, given a fixed set S, we present a deterministic algorithm that maintains—after i insertions into R—an O(1/δ⁰·⁶³¹)-approximate minimum-cost matching of cardinality i between R and S in arbitrary metric spaces. The algorithm achieves an amortized insertion time of O(n¹⁺ᵟ) per added point in R.To the best of our knowledge, this is the first constant-factor approximation algorithm for incremental minimum-cost matching that applies to general metric spaces and runs in update time sublinear in the number of edges of the underlying graph (which is n² in a metric space). Prior to our work, a comparable result was known only for constant-dimensional Euclidean spaces (Goranci et al., ICML 2025).
Short Bio: Syamantak Das is an Assistant Professor at IIIT-Delhi. He received his Ph.D. from IIT Delhi and subsequently spent two years in Germany as a postdoc at MPI-Informatik and University of Bremen. He works in the theory of algorithm design with a focus on approximation, online and dynamic algorithms for problems related to graphs and clustering.
