A tight bound on approximating arbitrary metrics by tree metrics

By Jittat Fakcharoenphol, Satish Rao, Kunal Talwar. Symposium on the Theory of Computing, 2003

1,006 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/ea8513648d61a30e04536e207a53dcb2025a62b4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

GEMSEC: Graph Embedding with Self Clustering (2018, background): “There is a long line of research in metric embedding – for example, embedding discrete metrics into trees [18] and into vector spaces [19].”
Geometric Approximation Algorithms (2011, background): “1 (which is originally from [FRT03]) is taken from [KLMN04].”
Minimizing Energies with Hierarchical Costs (2012, background): “They consider the class of r-hierarchically well-separated tree (r-HST) metrics (Bartal 1998) which are a special case of metrics defined above.”
Differentially private combinatorial optimization (2009, background): “[13], which guarantees that E[cost(E(R))] ≤ O(log n) · OPT; moreover, since the construction is oblivious to the set R, it preserves the privacy of the terminal pairs perfectly (i.”
The Design of Approximation Algorithms (2011, methodology): “Frans Schalekamp generated the image on the cover; it is an illustration of the tree metric algorithm of Fakcharoenphol, Rao, and Talwar [106] discussed in Section 8.5.”
Multiscale Wavelets on Trees, Graphs and High Dimensional Data: Theory and Applications to Semi Supervised Learning (2010, background): “Next, consider the following tree ultrametric, also popular for metric approximations (Bartal, 1996; 1998): Definition 3.1 Tree Metric: For any x, y ∈ X, define d(x, y) = ν(f older(x, y)) x = y 0 x = y (5) where f older(x, y) is the smallest folder in the tree containing both x, y.”
Optimal hierarchical decompositions for congestion minimization in networks (2008, methodology): “In this line of work [10, 11, 14, 16] which was initiated by Bartal [10] the node set of a graph equipped with the shortest path metric is given, and it is shown how to compute a probabilistic distribution over hierarchical decompositions such that the leaf-to-leaf distances in the corresponding dec”
Delay efficient sleep scheduling in wireless sensor networks (2005, result): “The following result is implicit in the work of Bartal [21], [ 22] and Fakcheroenphol, Rao, and Talwar [23]: Theorem7: ( [21], [22], [23]) There exists a collection S of c logn spanning trees of G such that for all nodesu, v in G,”
Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane (2011, background): “The results in [9, 6, 7] show low distortion bounds (probabilistic and average) for embedding arbitrary n point metrics into trees.”
MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts (2009, methodology): “Note that, unlike the problem of combining labelings of child nodes, in this case the moves ofα-expansion are no longer necessarily submodular.”
The Design of Competitive Online Algorithms via a Primal-Dual Approach (2009, result): “The group Steiner problem on general graphs: It is possible to combine the above theorem with the results of [46] on embedding a general metric (graph) in HSTs (similarly to what was done in the offline case).”
On the Utility of Privacy-Preserving Histograms (2004, background): “Moving to utility, there is a strong algorithmic literature on the power of probabilistic embeddings(see e.g. [25] [4] [6] [7] [9] [10] [18] [5] [23] [31]).”
Random Martingales and localization of maximal inequalities (2009, background): “[22] J. Fakcharoenphol, S. Rao, and K. Talwar.”