2026-07-24T14:49:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12648 2024-03-06T10:51:21Z ddc:004 open_access

Learning Lines with Ordinal Constraints Fan, Bohan Ihara, Diego Mohammadi, Neshat Sgherzi, Francesco Sidiropoulos, Anastasios Valizadeh, Mina metric learning embedding into the line ordinal constraints approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bohan Fan and Diego Ihara and Neshat Mohammadi and Francesco Sgherzi and Anastasios Sidiropoulos and Mina Valizadeh 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.45 urn:nbn:de:0030-drops-126486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.45 eng https://creativecommons.org/licenses/by/3.0/legalcode