Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

Gramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold, Eva Szilagyi, Da Wei Zheng
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:20162-20186, 2025.

Abstract

We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-goranci25a, title = {Fully Dynamic {E}uclidean Bi-Chromatic Matching in Sublinear Update Time}, author = {Goranci, Gramoz and Kiss, Peter and Patel, Neel and Seybold, Martin P. and Szilagyi, Eva and Zheng, Da Wei}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {20162--20186}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/goranci25a/goranci25a.pdf}, url = {https://proceedings.mlr.press/v267/goranci25a.html}, abstract = {We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.} }
Endnote
%0 Conference Paper %T Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time %A Gramoz Goranci %A Peter Kiss %A Neel Patel %A Martin P. Seybold %A Eva Szilagyi %A Da Wei Zheng %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-goranci25a %I PMLR %P 20162--20186 %U https://proceedings.mlr.press/v267/goranci25a.html %V 267 %X We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.
APA
Goranci, G., Kiss, P., Patel, N., Seybold, M.P., Szilagyi, E. & Zheng, D.W.. (2025). Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:20162-20186 Available from https://proceedings.mlr.press/v267/goranci25a.html.

Related Material