Randomized tree metrics
Kent Quanrud · 77:11
This lecture shows how to randomly embed any finite metric into a hierarchically structured tree so that every pair has expected stretch \(O(\log n)\). That reduction makes a long list of metric problems (buy-at-bulk,...