Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, Eva Szilagyi, Da Wei Zheng

International Conference on Machine Learning 2025 · Oral

This talk, presented at ICML 2025 by a collaborative team including Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, Eva Szilagyi, and Da Wei Zheng, addresses the challenging problem of **Fully Dynamic Euclidean Bi-Chromatic Matching**. The core of the presentation revolves around developing efficient algorithms to maintain an optimal or near-optimal matching between two sets of points (red and blue) in a Euclidean space, specifically when points are continuously inserted or deleted. This problem is particularly relevant to machine learning as its discrete version is equivalent to computing the **1-Wasserstein distance** between two probability distributions, a fundamental metric used in various ML tasks from data preprocessing and model selection to model evaluation.

AI review

A competent algorithms paper with a clean theoretical result — sublinear amortized update time for a 2-approximate fully dynamic Euclidean bichromatic matching, with a matching lower bound — presented at ICML under the framing of dynamic 1-Wasserstein computation. The core contribution is technically honest and the lower bound is genuinely satisfying, but the work sits squarely in the computational geometry / data structures literature and the ML framing feels opportunistic rather than organic. The experimental section is too vague to evaluate seriously, and the connection to ML practice is…