×

Hard metrics from Cayley graphs of abelian groups. (English) Zbl 1186.05067

Thomas, Wolfgang (ed.) et al., STACS 2007. 24th annual symposium on theoretical aspects of computer science, Aachen, Germany, February 22–24, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-70917-6/pbk). Lecture Notes in Computer Science 4393, 157-162 (2007).
Summary: Hard metrics are the class of extremal metrics with respect to embedding into Euclidean spaces: their distortion is as bad as it possibly gets, which is \(\Omega (\log n)\). Besides being very interesting objects akin to expanders and good codes, with rich structure of independent interest, 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 (see [N. Linial, E. London and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications”, Combinatorica 15, No. 2, 215–245 (1995; Zbl 0827.05021)] and [Y. Aumann and Y. Rabani, “An \(O(\log k)\) approximate min-cut max-flow theorem and approximation algorithm”, SIAM J. Comput. 27, No. 1, 291–301 (1998; Zbl 0910.05038)]). Recently, a different such family was found (see [S. Khot and A. Naor, “Nonembeddability theorems via Fourier analysis”, Math. Ann. 334, No. 4, 821–852 (2006; Zbl 1102.46051)], causing a certain excitement among the researchers in the area.
In this paper we present another construction of hard metrics, different from [Linial et al., loc. cit.; Aumann et al., loc. cit.] and more general, but clearer and simpler than [Khot and Naor, loc. cit.]. Our results naturally extend to NEG and to \(\ell _{1}\).
For the entire collection see [Zbl 1115.68007].

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20K99 Abelian groups
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI