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

DOI10.1137/18M1184400zbMATH Open1411.68079arXiv1808.02800MaRDI QIDQ4634019FDOQ4634019

Authors: Arnold Filtser 

Publication date: 7 May 2019

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

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|)$).

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

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

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)

Cites Work

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

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)