Efficient algorithms for Incremental Metric Bipartite Matching

The minimum-cost bipartite matching between two sets of points $R$ and $S$ in a metric space has a wide range of applications in machine learning, computer vision, and logistics. For instance, it can be used to estimate the $1$-Wasserstein distance between continuous probability distributions and for efficiently matching requests to servers while minimizing cost. However, the computational cost of determining the minimum-cost matching for general metrics spaces, poses a significant challenge, particularly in dynamic settings where points arrive over time and each update requires re-executing the algorithm. In this paper, given a fixed set $S$, we describe a deterministic algorithm that maintains, after $i$ additions to $R$, an $O(1/\delta^{0.631})$-approximate minimum-cost matching of cardinality $i$ between sets $R$ and $S$ in any metric space, with an amortized insertion time of $\widetilde{O}(n^{1+\delta})$ for adding points in $R$. To the best of our knowledge, this is the first algorithm for incremental minimum-cost matching that applies to arbitrary metric spaces. Interestingly, an important subroutine of our algorithm lends itself to efficient parallelization. We provide both a CPU implementation and a GPU implementation that leverages parallelism. Extensive experiments on both synthetic and real world datasets showcase that our algorithm either matches or outperforms all benchmarks in terms of speed while significantly improving upon the accuracy.