Probabilistic approximation of metric spaces and its algorithmic applications

By Y. Bartal. 1996

How researchers see this paper

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

Citations in the corpus

Scalable Fair Clustering (2019, methodology): “We build on the following result due to Bartal (1996), which gives a probabilistic embedding from R d to a γ -HST.”
A tight bound on approximating arbitrary metrics by tree metrics (2003, background): “Bartal [7, 8] constructed distributions over trees which were hierarchically well separated, and such trees are more conducive to design of divide-and-conquer type algorithms.”
Network topology generators: degree-based vs. structural (2002, methodology): “[5] Y. Bartal.”
A polylogarithmic approximation algorithm for the group Steiner tree problem (2000, methodology): “This is extended to arbitrary graphs by using the result of [3], and the nal approximation ratio is then O(log 3 n logk) (the size of the largest group, N , is at most the number of nodes n).”
Extending Lipschitz functions via random metric partitions (2005, background): “Let φ : R → R+ be any 2-Lipschitz map with supp(φ) ⊂ [(1) 2 , 4] and φ ≡ 1 on [1, 2].”
The Design of Approximation Algorithms (2011, methodology): “Bartal [39] defined the notion of the probabilistic approximation of metrics by tree metrics we use here, although his work was inspired by earlier unpublished work of Karp and work of Alon, Karp, Peleg, and West [7].”
On Privacy-Preserving Histograms (2005, background): “We now consider two classes of randomized histograms, and give bounds on the expected distance between any two histogram sanitized points, via bounds on E[% x] in terms of the t-radius of x. As argued in [ 2 , 10], expected distance bounds give useful bounds on any optimization problems whose output”
Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation (2001, methodology): “The breakthrough was made by Bartal, who gave a factor O(log n log log n) algorithm using a probabilistic approximation of metric spaces by tree metrics. After a slight improvement to a factor of O(log k log log k) [Charikar et al. 1998], a constant factor algorithm was recently obtained by Charikar”
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,”
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.”
Random Martingales and localization of maximal inequalities (2009, methodology): “[5] Y. Bartal.”
Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields (1999, methodology): “Consequently, we focus first on the case in which the metric on L corresponds to anr-hierarchically well-separated tree [2]; here, we formulate a linear programming relaxation and develop a rounding algorithm whose performance guarantee is a constant slightly larger than 2, depending on the separati”
Constrained mirror placement on the Internet (2001, methodology): “In [6], two graph theoretic algorithms, k-HST [18] and Min K-”
On the Utility of Privacy-Preserving Histograms (2004, background): “of equal size, in the natural fashion, recursing until each cell contains at most a single data point 2 . On the one hand, this resembles embedding into a tree [25, 6 , 5, 10, 23]: subdivision,We refer the reader to [24, 6 , 18, 27] for surveys of some these applications.”
IDMaps: a global internet host distance estimation service (2001, methodology): “More formal descriptions of these algorithms are available in [17], [18].”