{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,12,11]],"date-time":"2021-12-11T07:35:17Z","timestamp":1639208117478},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ITR ANI-0205445"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"\n We introduce a new notion of embedding, called\n minimum-relaxation ordinal embedding<\/jats:italic>\n , 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 we capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.\n <\/jats:p>","DOI":"10.1145\/1383369.1383377","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-21","source":"Crossref","is-referenced-by-count":6,"title":["Ordinal embeddings of minimum relaxation"],"prefix":"10.1145","volume":"4","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"Mihai","family":"B\u0103doiu","sequence":"additional","affiliation":[{"name":"Google Inc., NY, USA"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}]},{"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}]},{"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"AT&T Labs\u2014Research, Florham Park, NJ, USA"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[{"name":"MIT, Florham Park, Cambridge, MA, USA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795296334"},{"key":"e_1_2_1_2_1","volume-title":"Handbook of Combinatorics","author":"Alon N."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.30"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00076"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"B\u0103doiu M."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. 664--665","author":"Bartal Y."},{"key":"e_1_2_1_7_1","unstructured":"Barthelemy J.-P. and Guenoche A. 1991. Trees and Proximity Representations. John Wiley. Barthelemy J.-P. and Guenoche A. 1991. Trees and Proximity Representations. John Wiley."},{"key":"e_1_2_1_8_1","unstructured":"Bilu Y. and Linial N. 2004. Monotone maps sphericity and bounded second eigenvalue. arXiv:math.CO\/0401293. Bilu Y. and Linial N. 2004. Monotone maps sphericity and bounded second eigenvalue. arXiv:math.CO\/0401293."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 44th Symposium on Foundations of Computer Science. 514--523","author":"Brinkman B."},{"key":"e_1_2_1_11_1","volume-title":"Procedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 434--443","author":"B\u0103doiu M.","year":"2003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997866"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195296221"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2496(74)90027-3"},{"key":"e_1_2_1_15_1","first-page":"251","article-title":"Regul\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl","volume":"12","author":"Erd\u0151s P.","year":"1963","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320212"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188585"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010020"},{"key":"e_1_2_1_19_1","first-page":"285","article-title":"\/1967. The number of partitions of a set of N points in k dimensions induced by hyperplanes","author":"Harding E. F.","year":"1966","journal-title":"Proceedings of the Edinburgh Mathematical Society, Series"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00083-X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02291218"},{"key":"e_1_2_1_22_1","first-page":"177","article-title":"Low-distortion embeddings of finite metric spaces. In Handbook of Discrete and Computational Geometry, 2nd Ed., J. E. Goodman and J. O'Rourke, Eds. CRC Press","volume":"8","author":"Indyk P.","year":"2004","journal-title":"Chap."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289565"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289694"},{"key":"e_1_2_1_27_1","first-page":"745","article-title":"Embedding the diamond graph in Lp and dimension reduction in L1. Geome","volume":"14","author":"Lee J. R.","year":"2004","journal-title":"Funct. Anal."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_2_1_29_1","first-page":"589","article-title":"Bi-Lipschitz embeddings into low-dimensional Euclidean spaces","volume":"31","author":"Matou\u0161ek J.","year":"1990","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773799"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208008"},{"key":"e_1_2_1_32_1","unstructured":"Shah R. and Farach-Colton M. 2004. On the complexity of ordinal clustering. J. Classification. To appear. Shah R. and Farach-Colton M. 2004. On the complexity of ordinal clustering. J. Classification. To appear."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289630"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288916"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0226281-1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T21:17:40Z","timestamp":1613769460000},"score":1,"subtitle":["General properties, trees, and ultrametrics"],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383377"],"URL":"http:\/\/dx.doi.org\/10.1145\/1383369.1383377","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2008,8]]}}}