Published: July 3, 2009
Abstract: [Plain Text Version]
Hard metrics are the class of extremal metrics with respect to embedding into Euclidean spaces; they incur $\Omega(\log n)$ multiplicative distortion, which is as large as it can possibly get for any metric space of size $n$. Besides being very interesting objects akin to expanders and good error-correcting codes, and having a rich structure, such metrics are important for obtaining lower bounds in combinatorial optimization, e.g., on the value of MinCut/MaxFlow ratio for multicommodity flows.
For more than a decade, a single family of hard metrics was known (Linial, London, Rabinovich (Combinatorica 1995) and Aumann, Rabani (SICOMP 1998)). Recently, a different family was found by Khot and Naor (FOCS 2005).
In this paper we present a general method of constructing hard metrics. Our results extend to embeddings into negative type metric spaces and into $\ell_1.$
Licensed under a Creative Commons Attribution License (CC-BY)