Paper by Erik D. Demaine
- Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos, “Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics”, ACM Transactions on Algorithms, volume 4, number 4, August 2008, Article 46.
We introduce a new notion of embedding, called
minimum-relaxation ordinal embedding, parallel to the
standard notion of minimum-distortion (metric) embedding.
In an ordinal embedding, it is the relative order between pairs of distances,
and not the distances themselves, that must be preserved as much as possible.
The (multiplicative) relaxation of an ordinal embedding is the maximum ratio
between two distances whose relative order is inverted by the embedding.
We develop several worst-case bounds and approximation algorithms
on ordinal embedding. In particular, we establish that ordinal embedding
has many qualitative differences from metric embedding,
and capture the ordinal behavior of ultrametrics and
shortest-path metrics of unweighted trees.
- This paper is also available from the ACM Digital Library.
- The paper is 21 pages.
- The paper is available in PostScript (530k), gzipped PostScript (224k), and PDF (286k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Ordinal_APPROX2008 (Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction)
- Ordinal_SODA2005 (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 September 2, 2021 by