Title: Steiner Point Removal with distortion O( log k ), using the Relaxed Voronoi algorithm

Speaker: Arnold Filtser, Computer Science Department, Ben-Gurion University of the Negev, Israel

Time & Location: 12pm - 1pm, Monday (May 20) @ NCS 120

Abstract: 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 Relaxed Voronoi algorithm) which incurs distortion O( log k ). This algorithm can be implemented in almost linear time ( O( |E| log |V| ) ).

(see https://arxiv.org/abs/1808.02800 and https://epubs.siam.org/doi/abs/10.1137/18M1184400)   

Bio: Arnold Filtser is a PhD student in the Department of Computer Science of Ben-Gurion University, and works with Profs. Ofer Neiman and Robert Krauthgamer. His research interests are in theoretical computer science, particularly, in metric spaces, low-distortion embeddings, and randomized and approximation algorithms.