Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families

Douglas E. Carroll, Ashish Goel

It was shown recently by Fakcharoenphol et al that arbitrary finite metrics can be embedded into distributions over tree metrics with distortion O(log n). It is also known that thi…