Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics

Noga Alon, Mihai Bǎdoiu, Erik D. Demaine, Martin Farach-Colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations

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.

Original languageEnglish (US)
Pages650-659
Number of pages10
StatePublished - Jul 1 2005
Externally publishedYes
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics'. Together they form a unique fingerprint.

Cite this