DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.36

Computing Bi-Lipschitz Outlier Embeddings into the Line

Authors: Karine Chubarian and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

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.

Cite as

Karine Chubarian and Anastasios Sidiropoulos. Computing Bi-Lipschitz Outlier Embeddings into the Line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chubarian_et_al:LIPIcs.APPROX/RANDOM.2020.36,
  author =	{Chubarian, Karine and Sidiropoulos, Anastasios},
  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 =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.36},
  URN =		{urn:nbn:de:0030-drops-126398},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.36},
  annote =	{Keywords: metric embeddings, outliers, distortion, approximation algorithms}
}

Search Results

Documents authored by Chubarian, Karine

Computing Bi-Lipschitz Outlier Embeddings into the Line

Abstract

Cite as

Thanks for your feedback!

Could not send message