Paper by Erik D. Demaine

Reference:

Mihai Bădoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, and Morteza Zadimoghaddam, “Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction”, in Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), Boston, Massachusetts, August 25–27, 2008, pages 21–34.

Abstract:

This paper studies how to optimally embed a general metric, represented by a graph, into a target space while preserving the relative magnitudes of most distances. More precisely, in an ordinal embedding, we must preserve the relative order between pairs of distances (which pairs are larger or smaller), and not necessarily the values of the distances themselves. The relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. We develop polynomial-time constant-factor approximation algorithms for minimizing the relaxation in an embedding of an unweighted graph into a line metric and into a tree metric. These two basic target metrics are particularly important for representing a graph by a structure that is easy to understand, with applications to visualization, compression, clustering, and nearest-neighbor searching. Along the way, we improve the best known approximation factor for ordinally embedding unweighted trees into the line down to 2. Our results illustrate an important contrast to optimal-distortion metric embeddings, where the best approximation factor for unweighted graphs into the line is O(n^1/2), and even for unweighted trees into the line the best is Õ(n^1/3). We also show that Johnson-Lindenstrauss-type dimensionality reduction is possible with ordinal relaxation and ℓ₁ metrics (and ℓ_p metrics with 1 ≤ p ≤ 2), unlike metric embedding of ℓ₁ metrics.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 14 pages.

Availability:

The paper is available in PostScript (387k), gzipped PostScript (164k), and PDF (217k).

See information on file formats.

[Google Scholar search]

Related papers:

Ordinal_TAlg (Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics)