Paper by Erik D. Demaine
- 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.
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(n1/2), and even for unweighted trees into the line
the best is Õ(n1/3). We also show that
Johnson-Lindenstrauss-type dimensionality reduction is possible with ordinal
relaxation and ℓ1 metrics (and ℓp
metrics with 1 ≤ p ≤ 2), unlike metric
embedding of ℓ1 metrics.
- This paper is also available from SpringerLink.
- The paper is 14 pages.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 27, 2019 by