Light Spanners
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
New construction claims lightness O(n^{1/k}) while keeping stretch about 2k (more precisely a (2+ε)·k-style bound in the paper) and number of edges ≈ n^{1+1/k}. Key tools are hierarchical clustering of the MST and bucketing edges by weight, then contracting clusters and running a greedy spanner on each contracted graph; rounding MST edge weights with dummy nodes handles uniformity. A simpler version gives lightness K·n^{1/k}, improved by merging high-degree clusters to remove the extra K factor.
AI-written summary · about