##### Steiner Point Removal with distortion $O(\log k)$, using the Noisy-Voronoi algorithm
In the Steiner Point Removal (SPR) problem, we are given a weighted graph $G=(V,E)$ and a set of terminals $K\subset V$ of size $k$. The objective is to find a minor $M$ of $G$ with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer and Nguyen [SICOMP2015] devised a ball-growing algorithm with exponential distributions to show that the distortion is at most $O(\log^5 k)$. Cheung [SODA2018] improved the analysis of the same algorithm, bounding the distortion by $O(\log^2 k)$. We devise a novel and simpler algorithm (called the Noisy Voronoi algorithm) which incurs distortion $O(\log k)$. This algorithm can be implemented in almost linear time ($O(|E|\log |V|)$).
###### NurtureToken New!

Token crowdsale for this paper ends in

###### Author

Are you an author of this paper? Check the Twitter handle we have for you is correct.

###### Read it. Rate it.
#1. Which part of the paper did you read?

#2. The paper contains new data or analyses that is openly accessible?
#3. The conclusion is supported by the data and analyses?
#4. The conclusion is of scientific interest?
#5. The result is likely to lead to future research?

User:
Repo:
Stargazers:
0
Forks:
0
Open Issues:
0
Network:
0
Subscribers:
0
Language:
None
Views:
0
Likes:
0
Dislikes:
0
Favorites:
0
0
###### Other
Sample Sizes (N=):
Inserted:
Words Total:
Words Unique:
Source:
Abstract:
None
08/08/18 05:52PM
17,096
2,892
###### Tweets
ComputerPapers: Steiner Point Removal with distortion $O(\log k)$, using the Noisy-Voronoi algorithm. https://t.co/ddsFdMxxS4