License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12648/
Go to the corresponding LIPIcs Volume Portal

Fan, Bohan ; Ihara, Diego ; Mohammadi, Neshat ; Sgherzi, Francesco ; Sidiropoulos, Anastasios ; Valizadeh, Mina

Learning Lines with Ordinal Constraints

pdf-format:
LIPIcs-APPROX45.pdf (0.5 MB)

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
Collection: 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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI