A tight bound on approximating arbitrary metrics by tree metrics

DOI10.1145/780542.780608zbMath1192.68977OpenAlexW2082353536MaRDI QIDQ5901089

No author found.

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780608

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Related Items (72)

Absolute Lipschitz extendability ⋮ Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median ⋮ A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ New approximation algorithms for the unsplittable capacitated facility location problem ⋮ A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem ⋮ New length bounds for cycle bases ⋮ Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ Serving Online Requests with Mobile Servers ⋮ Streaming Embeddings with Slack ⋮ Mixed Hölder matrix discovery via wavelet shrinkage and Calderón-Zygmund decompositions ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Optimal random matchings, tours, and spanning trees in hierarchically separated trees ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Optimal cuts and partitions in tree metrics in polynomial time ⋮ Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane ⋮ Strategies for parallel unaware cleaners ⋮ Pattern matching under DTW distance ⋮ Randomized oblivious integral routing for minimizing power cost ⋮ On Metric Clustering to Minimize the Sum of Radii ⋮ Spanners of bounded degree graphs ⋮ Maximum gradient embeddings and monotone clustering ⋮ Sublinear time algorithms for earth mover's distance ⋮ Unnamed Item ⋮ Affine and projective tree metric theorems ⋮ Euclidean distortion and the sparsest cut ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Shifting strategy for geometric graphs without geometry ⋮ Low dimensional embeddings of ultrametrics. ⋮ On the efficiency of routing in sensor networks ⋮ Enhanced negative type for finite metric trees ⋮ Algorithms for the universal and a priori TSP ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Advances in metric embedding theory ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ The mixed Lipschitz space and its dual for tree metrics ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ On the Facility Location Problem in Online and Dynamic Models. ⋮ Survey on Oblivious Routing Strategies ⋮ Approximating \(k\)-hop minimum spanning trees in Euclidean metrics ⋮ On metric clustering to minimize the sum of radii ⋮ Approximating \(k\)-hop minimum-spanning trees ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Extending Lipschitz functions via random metric partitions ⋮ Online and offline algorithms for the sorting buffers problem on the line metric ⋮ On the graph turnpike problem ⋮ Approximability of unsplittable shortest path routing problems ⋮ Approximating snowflake metrics by trees ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Quasimetric embeddings and their applications ⋮ Collective Additive Tree Spanners of Homogeneously Orderable Graphs ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Constant-Factor FPT Approximation for Capacitated k-Median ⋮ Local embeddings of metric spaces ⋮ Volume distortion for subsets of Euclidean spaces ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Analysis on Laakso graphs with application to the structure of transportation cost spaces ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ Improved approximation algorithms for the single-sink buy-at-bulk network design problems ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ The polymatroid Steiner problems ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ Unnamed Item ⋮ A greedy approximation algorithm for the group Steiner problem ⋮ Gromov-Hausdorff approximation of filamentary structures using Reeb-type graphs ⋮ To close is easier than to open: dual parameterization to \(k\)-median ⋮ A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem

This page was built for publication: A tight bound on approximating arbitrary metrics by tree metrics