Dieses Jahr erhielt die ICML über 12.000 Einreichungen, mit einer Annahmequote von 26,9 %. Von den akzeptierten Beiträgen wurden nur 120 für Vorträge ausgewählt, was die besten ~1 % aller Einreichungen repräsentiert.
Das Paper ist eine Zusammenarbeit zwischen Gramoz Goranci, Peter Kiss, Martin P. Seybold und Eva Szilagyi (Subeinheit TAA – Theory and Application of Algorithms, Universität Wien), Neel Patel (University of Southern California) und Da Wei Zhang (University of Illinois Urbana-Champaign).
Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
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 ε > 0, our algorithm achieves O(1/ε)-approximation and handles updates in O(nε) 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.