Dimension reduction for finite trees in ℓ1
James R. Lee, Arnaud de Mesmay, Mohammad Moharrami · 2012
We that every n-point tree metric admits a (1 + ε)-embedding into ℓ1C(ε)log n, for every ε > 0, where C(ε) ≤ . This matches the natural volume lower bound up to a factor depending only on ε. Previously it was unknown whether even complete binary trees on n nodes could be embedded in ℓ1O(log n) with O(1) distortion. For complete d-ary trees, our construction achieves .