Efficient Algorithms For Fully Dynamic Bipartite Matching In Metric Spaces

We consider the problem of maintaining a minimum-cost bipartite matching between two point sets $A$ and $B$ in a metric space $(\mathbb{X},\mathsf{d})$ under insertions and deletions of input points. The Wasserstein-$p$ ($W_p$) cost of a matching $M$ is defined as $({\sum }_{(a,b)\in M}\mathsf{d}(a,b{)}^p{)}^{1/p}$ and an $\alpha$-approximate matching is one whose total cost is at most $\alpha$ times the cost of a minimum-cost matching. We obtain two main results. If $A$ and $B$ are points in ${\mathbb{R}}^d$ and the distance between two points is measured under the ${\ell }_p$-metric, an $O(d{ϵ}^{-3/2})$-approximate $W_1$-matching between $A$ and $B$ can be maintained with an amortized $O(n^{ϵ}d{ϵ}^{-3/2}\phi (n,1/\sqrt{ϵ}))$ update time, for any parameter $ϵ\in (0,1]$, and where $\phi (n,1/\sqrt{ϵ})$ denotes the update time of a ${ϵ}^{-1/2}$-approximate nearest neighbor data structure. For the ${\ell }_2$ norm this results in an update time of $O((d+{ϵ}^{-3/2}{n}^{ϵ})\log n)$. The current state-of-the-art for high-dimensional settings only focus on the ${\ell }_2$-metric and maintain an $O(\log n)$-approximate matching. Our result not only extends to any ${\ell }_p$ norm, but it also improves the approximation factor for $d=o(\log n)$ under the ${\ell }_2$-metric. Next, we consider the problem of maintaining a $W_p$-matching when $A$ and $B$ are point sets in an arbitrary finite metric space. We show that for any $k,p\ge 1$ and constant $ϵ>0$, a $2k(1+ϵ)$-approximate matching can be maintained with an amortized update time of $O(k{n}^{1+1/k}{ϵ}^{-1}\log \Delta )$, where $\Delta$ is the spread of $A\cup B$. Prior work on finite metric spaces gave an insertion-only data structure for $W_1$-matching. In contrast, we develop a fully dynamic approach that supports both insertions and deletions and work for all $W_p$-matchings. Together, our results extend dynamic Wasserstein matching beyond fixed-dimensional $W_1$ settings: they handle high-dimensional geometric instances, extend prior insertion-only $1$-Wasserstein matching guarantees to the fully dynamic setting, and support $p$-Wasserstein costs for every integer $p\ge 1$ in arbitrary metric spaces.