Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

on YouTube ↗28m

" summary

Produces a constant-factor approximation to the Euclidean MST on n points in Rd using a new MPC algorithm that runs in O~(loglog n) rounds with near-linear total space and sublinear local memory. Key ingredients are building a sparse spanner, using geometric space partitions (quadtree-like cells) to create supernodes, and accelerating connectivity via leader-compression so remaining merges cost little; extends to a O~(loglog n)-round TSP approximation.

AI-written summary · about

" chapters (13)

1. 0:00Euclidean MST in MPC
2. 1:30MPC model and constraints
3. 3:20Low vs high-dim MST work
4. 8:00Spanner and tree embedding
5. 9:49Proposed algorithm overview
6. 11:00Kruskal’s algorithm and graphs
7. 12:30Leader compression in MPC
8. 15:25Geometry for leader compression
9. 20:31Proof and large components
10. 23:33Gap instances and levels
11. 25:22Non-gap divide and conquer
12. 26:32Open problems
13. 27:59Q&A