Research map / Learning theory and algorithms / Prediction and decision losses
Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Presents the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time, maintaining an O(1/ε)-approximate matching in O(n^ε/ε) worst-case update time via a bottom-up quadtree-style (p-tree) implicit matching scheme.
Problem
Maintaining a high-quality minimum-cost Euclidean bi-chromatic matching under point insertions and deletions, motivated by estimating the 1-Wasserstein distance on evolving distributions, where prior dynamic geometric matching required linear update time.
Approach
Bottom-up implicit matching on a restricted p-tree: at each cell, unmatched excess points are forwarded as cardinalities represented by cell centers, and each update only re-solves a geometric transportation problem on O(p^2) cell centers along one root-to-leaf path, giving O(n^ε/ε) update time.
Key results
- Dynamic algorithm achieves expected O(1/ε)-approximation with O(n^ε · ε^{-1}) worst-case update time for insertions and deletions in R^2.
- Experiments show dynamic updates typically take one to ten milliseconds and the approximate cost stays within a factor below 2 of exact minimum cost in practice.
- Proves no dynamic algorithm can achieve a (2-δ)-approximation with sublinear update time, even with only insertions or only deletions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use dynamic updates instead of periodic static recomputation | Proposed dynamic algorithm · Uniform vs Uniform; Uniform vs Gaussian; Taxi Pickup vs Dropoff | runtime | Helped |
| use the dynamic algorithm's approximate matching rather than the exact minimum-cost matching | Proposed dynamic algorithm · Uniform vs Uniform; Uniform vs Gaussian | matching cost ratio: <2 | Hurt |
| reduce ε | Proposed dynamic algorithm · Uniform vs Uniform; Uniform vs Gaussian | approximation quality | Mixed |
| vary p across 2, 4, 8, 16, and 32 (ablation) | Proposed dynamic algorithm · Uniform vs Uniform; Uniform vs Gaussian; Taxi Pickup vs Dropoff | approximation quality and update time | Mixed |
| maintain a matching dynamically on Taxi trips in a sliding window | Proposed dynamic algorithm · Taxi Pickup vs Dropoff | monitoring distributional drift | Helped |
Surprising findings
- No sublinear-update dynamic algorithm can achieve a (2-δ)-approximation, so a constant-factor loss is unavoidable.
- In the dynamic setting, the simple repeat-and-take-best trick for high-probability guarantees does not apply.
Limitations
- Approximation guarantee holds only in expectation, not with high probability in the dynamic setting.
- Analysis stated for d=2 with spread bounded by poly(n); extension to higher constant d is claimed but not the focus.
- Experiments are single-threaded on a single machine using synthetic and one real dataset.
Experimental setup
Datasets: NYC Yellow Cab taxi trips December 2009 synthetic Uniform points on integers 1-500 synthetic Gaussian points
Benchmarks: Uniform vs Uniform Uniform vs Gaussian NYC Taxi pickup vs dropoff
Metrics: update time speedup over static recomputation empirical 1-Wasserstein distance approximation ratio vs exact cost
Baselines: Hungarian algorithm static approximate matching (Chen et al.) static recomputation of matching
Builds on: Chen et al. static top-down quadtree matching (O(n^{1+ε}) approximation) Sharathkumar-Agarwal style Euclidean transportation solver restricted p-tree dynamic maintenance
Closest papers by meaning
- A Robust Exact Algorithm for the Euclidean Bipartite Matching Problem (NeurIPS 2023 · similarity 0.91)
- Proportionally Fair Matching via Randomized Rounding (AAAI 2025 · similarity 0.84)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.83)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.83)
- Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem (NeurIPS 2024 · similarity 0.82)
- Graph Alignment via Birkhoff Relaxation (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.