Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.45
URN: urn:nbn:de:0030-drops-126486
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12648/
Fan, Bohan ; Ihara, Diego ; Mohammadi, Neshat ; Sgherzi, Francesco ; Sidiropoulos, Anastasios ; Valizadeh, Mina
Learning Lines with Ordinal Constraints
| pdf-format: |
|
Abstract
We study the problem of finding a mapping f from a set of points into the real line, under ordinal triple constraints. An ordinal constraint for a triple of points (u,v,w) asserts that |f(u)-f(v)| < |f(u)-f(w)|. We present an approximation algorithm for the dense case of this problem. Given an instance that admits a solution that satisfies (1-ε)-fraction of all constraints, our algorithm computes a solution that satisfies (1-O(ε^{1/8}))-fraction of all constraints, in time O(n⁷) + (1/ε)^{O(1/ε^{1/8})} n.
BibTeX - Entry
@InProceedings{fan_et_al:LIPIcs:2020:12648,
author = {Bohan Fan and Diego Ihara and Neshat Mohammadi and Francesco Sgherzi and Anastasios Sidiropoulos and Mina Valizadeh},
title = {{Learning Lines with Ordinal Constraints}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {45:1--45:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12648},
URN = {urn:nbn:de:0030-drops-126486},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.45},
annote = {Keywords: metric learning, embedding into the line, ordinal constraints, approximation algorithms}
}
| Keywords: | metric learning, embedding into the line, ordinal constraints, approximation algorithms | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 11.08.2020 | |
| Supplementary Material: | https://github.com/lnghrdntcr/lloc |
