Steiner Point Removal with Distortion O(log k)
Arnold Filtser · Society for Industrial and Applied Mathematics eBooks · 2018
In the Steiner point removal (SPR) problem, we are given a weighted graph G = (V, E) and a set of terminals K ⊂ V of size k. The objective is to find a minor M of G with only the terminals as its vertex set, such that the distance between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer and Nguyen [KKN15] used a ball-growing algorithm with exponential distributions to show that the distortion is at most O(log5 k). Cheung [Che18] improved the analysis of the same algorithm, bounding the distortion by O(log2 k). We improve the analysis of this ball-growing algorithm even further, bounding the distortion by O(log k).