Paper by Erik D. Demaine

Reference:

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”, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 650–659.

BibTeX

@InProceedings{Ordinal_SODA2005,
  AUTHOR        = {Noga Alon and Mihai B\u{a}doiu and Erik D. Demaine and
                   Martin Farach-Colton and MohammadTaghi Hajiaghayi and
                   Anastasios Sidiropoulos},
  TITLE         = {Ordinal Embeddings of Minimum Relaxation:
                   General Properties, Trees, and Ultrametrics},
  BOOKTITLE     = {Proceedings of the 16th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2005)},
  bookurl       = {http://www.siam.org/meetings/DA05/},
  ADDRESS       = {Vancouver, British Columbia, Canada},
  MONTH         = {January 23--25},
  YEAR          = 2005,
  PAGES         = {650--659},

  withstudent   = 1,
  length        = {10 pages},
  papers        = {Ordinal_TAlg; Ordinal_APPROX2008},
  dblp          = {https://dblp.org/rec/conf/soda/AlonBDFHS05},
  ee            = {https://dl.acm.org/doi/10.5555/1070432.1070523},
  comments      = {This paper is also available from <A HREF="https://dl.acm.org/doi/10.5555/1070432.1070523">ACM</A>.},
}

Abstract:

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.

Comments:

This paper is also available from ACM.

Length:

The paper is 10 pages.

Availability:

The paper is available in PostScript (344k), gzipped PostScript (128k), and PDF (192k).

See information on file formats.

[Google Scholar search]

Related papers:

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

Ordinal_APPROX2008 (Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction)