Reproduce “Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Gramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold, Eva Szilagyi, Da Wei Zheng
Researchers at the University of Vienna developed the first fully dynamic algorithm for Euclidean bi-chromatic matching, achieving sub-linear O(n^ε * ε^-1) worst-case update time while providing an O(1/ε)-approximate solution. This approach demonstrated orders of magnitude faster performance compared to static recomputation, accurately estimating the 1-Wasserstein distance for datasets up to 1,000,000 points.
Key insights
- Sub-linear update times for dynamic geometric matching can be achieved by extending static approximation algorithms, particularly by leveraging nested grid structures and bottom-up processing.
- Representing and matching "excess points" implicitly through an Euclidean Transportation Problem, rather than explicitly, is crucial for maintaining efficiency under updates.
- The inherent hardness of dynamic geometric matching (demonstrated by a (2-δ)-approximation lower bound for sub-linear updates) necessitates and justifies an O(1/ε) approximation ratio.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.