Fast approximation in subspaces by doubling metric decomposition

DOI10.1007/978-3-642-15775-2_7MaRDI QIDQ3586452zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Łukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15775-2_7

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Sublinear time algorithms for metric space problems
• A PTAS for the Steiner forest problem in doubling metrics
• Fast, precise and dynamic distance queries
• Fast construction of nets in low dimensional metrics, and their applications
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications

Cited in

(4)

• On random perfect matchings in metric spaces with not-too-large diameters
• Speeding up spatial approximation search in metric spaces
• Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1
• Metric selection in fast dual forward-backward splitting

This page was built for publication: Fast approximation in subspaces by doubling metric decomposition

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