A tight bound on approximating arbitrary metrics by tree metrics
From MaRDI portal
Publication:5917578
DOI10.1016/j.jcss.2004.04.011zbMath1071.68082OpenAlexW3030774092MaRDI QIDQ5917578
No author found.
Publication date: 18 November 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.011
Related Items
Wasserstein distance and metric trees, Labelings vs. embeddings: on distributed and prioritized representations of distances, A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case, The ultrametric Gromov-Wasserstein distance, Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions, Approximation algorithms for fair \(k\)-median problem without fairness violation, On approximating tree spanners that are breadth first search trees, On Locality-Sensitive Orderings and Their Applications, Bounded Degree Group Steiner Tree Problems, $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm, A randomized algorithm for the on-line weighted bipartite matching problem, On approximating degree-bounded network design problems, A poly-log competitive posted-price algorithm for online metrical matching on a spider, A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line, Approximation algorithms for requirement cut on graphs, Minimum-Cost Network Design with (Dis)economies of Scale, Online network design with outliers, Metric embedding, hyperbolic space, and social networks, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Optimal (Euclidean) Metric Compression, Covering metric spaces by few trees, Terminal embeddings, Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems, Lossless Prioritized Embeddings, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Prioritized Metric Structures and Embedding, Metric decompositions of path-separable graphs, On generalizations of the parking permit problem and network leasing problems, A \(o(n)\)-competitive deterministic algorithm for online matching on a line, Group parking permit problems, Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem, Stochastic approximation of lamplighter metrics, Approximation algorithms for Steiner forest: An experimental study, Thresholded covering algorithms for robust and max-min optimization, Reliable Spanners for Metric Spaces, An introduction to the Ribe program, A polylogarithmic approximation for computing non-metric terminal Steiner trees, Tree spanners of bounded degree graphs, Unnamed Item, Unnamed Item, \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees, Dynamic vs. oblivious routing in network design, Unnamed Item, UPGMA and the normalized equidistant minimum evolution problem, Pathwidth, trees, and random embeddings, \(d\)-dimensional arrangement revisited, Watchman routes for lines and line segments, The \(k\)-server problem, A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics, Algorithms for the universal and a priori TSP, Network design with a discrete set of traffic matrices, Spanners in sparse graphs, A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching, Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm, On average distortion of embedding metrics into the line, On the hardness of full Steiner tree problems, Approximating \(k\)-generalized connectivity via collapsing HSTs, On Locality-Sensitive Orderings and Their Applications, Approximation Algorithms for Single and Multi-Commodity Connected Facility Location, Optimal nearest neighbor queries in sensor networks, A unified framework of FPT approximation algorithms for clustering problems, Parametrized Metrical Task Systems, Virtual machine placement for minimizing connection cost in data center networks, THE MINIMUM GUARDING TREE PROBLEM, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Local search algorithms for the red-blue median problem, Discrete and continuous models for partitioning problems, Distributed transactional memory for general networks, Online computation with advice, Deterministic sampling algorithms for network design, Improved approximation for fractionally subadditive network design, A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design, Ramsey-type theorems for metric spaces with applications to online problems, Random martingales and localization of maximal inequalities, Bayesian ignorance, Unnamed Item, Randomly removing \(g\) handles at once, An improved approximation algorithm for requirement cut, Ramsey partitions and proximity data structures, Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph, Efficient distributed approximation algorithms via probabilistic tree embeddings, Unbalanced graph cuts with minimum capacity, Online \(k\)-taxi via double coverage and time-reverse primal-dual, A simple algorithm for the multiway cut problem, Unnamed Item, Approximation algorithms for replenishment problems with fixed turnover times, Online \(k\)-taxi via double coverage and time-reverse primal-dual, Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees, Covering Metric Spaces by Few Trees, Stochastic Online Metric Matching, Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation, The minimum degree group Steiner problem, Approximating fault-tolerant group-Steiner problems, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, The ordered \(k\)-median problem: surrogate models and approximation algorithms, On notions of distortion and an almost minimum spanning tree with constant average distortion, Simplex Transformations and the Multiway Cut Problem, A note on the subadditive network design problem, Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing, Non-approximability of weighted multiple sequence alignment for arbitrary metrics, Randomized algorithm for the \(k\)-server problem on decomposable spaces, Cutting Corners Cheaply, or How to Remove Steiner Points, On Hop-Constrained Steiner Trees in Tree-Like Metrics, An analysis framework for distributed hierarchical directories, On fixed cost \(k\)-flow problems
Cites Work
- On Lipschitz embedding of finite metric spaces in Hilbert space
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- On approximating planar metrics by tree metrics.
- The geometry of graphs and some of its algorithmic applications
- Packing directed circuits fractionally
- Measured descent: A new embedding method for finite metrics
- Competitive concurrent distributed queuing
- Better algorithms for unfair metrical task systems and applications
- Optimum Communication Spanning Trees
- Approximation algorithms for classification problems with pairwise relationships
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Online tracking of mobile users
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- A lower bound on the distortion of embedding planar metrics into Euclidean space
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximating min-sum k -clustering in metric spaces
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Excluded minors, network decomposition, and multicommodity flow
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
