Volume 5 (2009) Article 6 pp. 125-134
Hard Metrics from Cayley Graphs of Abelian Groups
by
Published: July 3, 2009
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.
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.$