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.36
URN: urn:nbn:de:0030-drops-126398
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12639/
Go to the corresponding LIPIcs Volume Portal

Chubarian, Karine ; Sidiropoulos, Anastasios

Computing Bi-Lipschitz Outlier Embeddings into the Line

pdf-format:
LIPIcs-APPROX36.pdf (0.6 MB)

Abstract

The problem of computing a bi-Lipschitz embedding of a graphical metric into the line with minimum distortion has received a lot of attention. The best-known approximation algorithm computes an embedding with distortion O(c²), where c denotes the optimal distortion [Bădoiu et al. 2005]. We present a bi-criteria approximation algorithm that extends the above results to the setting of outliers.
Specifically, we say that a metric space (X,ρ) admits a (k,c)-embedding if there exists K ⊂ X, with |K| = k, such that (X⧵ K, ρ) admits an embedding into the line with distortion at most c. Given k ≥ 0, and a metric space that admits a (k,c)-embedding, for some c ≥ 1, our algorithm computes a (poly(k, c, log n), poly(c))-embedding in polynomial time. This is the first algorithmic result for outlier bi-Lipschitz embeddings. Prior to our work, comparable outlier embeddings where known only for the case of additive distortion.

BibTeX - Entry

@InProceedings{chubarian_et_al:LIPIcs:2020:12639,
  author =	{Karine Chubarian and Anastasios Sidiropoulos},
  title =	{{Computing Bi-Lipschitz Outlier Embeddings into the Line}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{36:1--36:21},
  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/12639},
  URN =		{urn:nbn:de:0030-drops-126398},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.36},
  annote =	{Keywords: metric embeddings, outliers, distortion, approximation algorithms}
}

Keywords: metric embeddings, outliers, distortion, approximation algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

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