Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910943136448512 |
|---|---|
| author | Goranci, Gramoz Kiss, Peter Patel, Neel Seybold, Martin P. Szilagyi, Eva Zheng, Da Wei |
| author_facet | Goranci, Gramoz Kiss, Peter Patel, Neel Seybold, Martin P. Szilagyi, Eva Zheng, Da Wei |
| contents | 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 sub-linear 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09010 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time Goranci, Gramoz Kiss, Peter Patel, Neel Seybold, Martin P. Szilagyi, Eva Zheng, Da Wei Data Structures and Algorithms 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 sub-linear 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. |
| title | Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.09010 |