Steiner point removal with distortion O( k) using the \texttt{Relaxed-Voronoi} algorithm

DOI10.1137/18M1184400MaRDI QIDQ4634019zbMATH OpenFDO

Authors Arnold Filtser

Publication date 7 May 2019

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.02800

zbMATH Keywords

randomized algorithmdistortionmetric embeddingminor graphSteiner point removal (SPR)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance in graphs (05C12) Graph minors (05C83)

Abstract: In the Steiner Point Removal (SPR) problem, we are given a weighted graph $G=(V,E)$ and a set of terminals $KsubsetV$ 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(lo{g}^{5}k)$. Cheung [SODA2018] improved the analysis of the same algorithm, bounding the distortion by $O(lo{g}^{2}k)$. We devise a novel and simpler algorithm (called the Noisy Voronoi algorithm) which incurs distortion $O(logk)$. This algorithm can be implemented in almost linear time ($O(|E|log|V|)$).

Recommendations

• Steiner point removal with distortion \(O(\log k)\)
• Steiner point removal -- distant terminals don't (really) bother
• Cutting corners cheaply, or how to remove Steiner points
• Cutting Corners Cheaply, or How to Remove Steiner Points
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees

Cites work

• scientific article; zbMATH DE number 432834 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 2079348 (Why is no real title available?)
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees
• A tight bound on approximating arbitrary metrics by tree metrics
• An improved approximation algorithm for requirement cut
• Approximate distance oracles
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Approximation Algorithms for the 0-Extension Problem
• Automata, Languages and Programming
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Extensions and limits to vertex sparsification
• Fibonacci heaps and their uses in improved network optimization algorithms
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Graph spanners
• Improved guarantees for vertex sparsification in planar graphs
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• Mimicking Networks and Succinct Representations of Terminal Cuts
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• On vertex sparsifiers with Steiner nodes
• Refined vertex sparsifiers of planar graphs
• Small Stretch Pairwise Spanners
• Sparse source-wise and pair-wise distance preservers
• Steiner point removal -- distant terminals don't (really) bother
• Steiner point removal with distortion \(O(\log k)\)
• Steiner points in tree metrics don't (really) help
• Terminal embeddings
• Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
• Twice-Ramanujan sparsifiers
• Vertex sparsifiers: new results from old techniques

Cited in

(8)

• Cutting corners cheaply, or how to remove Steiner points
• Relaxed Voronoi: a simple framework for terminal-clustering problems
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Steiner point removal -- distant terminals don't (really) bother
• Steiner point removal with distortion \(O(\log k)\)
• Online Spanners in Metric Spaces
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees

This page was built for publication: Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634019)