Volume 5 (2009) Article 6 pp. 125-134
Hard Metrics from Cayley Graphs of Abelian Groups
by
Received: April 29, 2008
Published: July 3, 2009
Download article from ToC site:
[PDF (193K)] [PS (529K)] [Source ZIP]
Keywords: metric embedding, hard metrics, lower bounds
ACM Classification: F.2.2, G.2.2
AMS Classification: 11J83, 52C45, 05C25

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.$