Relaxed Voronoi: a simple framework for terminal-clustering problems

DOI10.4230/OASICS.SOSA.2019.10MaRDI QIDQ6593565zbMATH OpenFDO

Authors Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi

Publication date 26 August 2024

Full work available at URL https://doi.org/10.4230/OASICS.SOSA.2019.10

zbMATH Keywords

clusteringdoubling dimensionzero extensionrelaxed VoronoiSteiner-point removal

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Metric embeddings as related to computational problems and algorithms (68R12)

Recommendations

• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Metric clustering via consistent labeling
• Cutting corners cheaply, or how to remove Steiner points
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Approximation algorithms for the 0-extension problem

Cited in

(3)

• Scattering and sparse partitions, and their applications
• Scattering and sparse partitions, and their applications
• Optimal padded decomposition for bounded treewidth graphs

This page was built for publication: Relaxed Voronoi: a simple framework for terminal-clustering problems

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