Light Euclidean spanners with Steiner points
The FOCS'19 paper of Le and Solomon, culminating a long line of research on Euclidean
spanners, proves that the lightness (normalized weight) of the greedy $(1+\epsilon) …
spanners, proves that the lightness (normalized weight) of the greedy $(1+\epsilon) …
Metric embeddings with outliers
We initiate the study of metric embeddings with outliers. Given some finite metric space we
wish to remove a small set of points and to find either an isometric or a low-distortion …
wish to remove a small set of points and to find either an isometric or a low-distortion …
Probabilistic embeddings of the Fréchet distance
A Driemel, A Krivošija - International Workshop on Approximation and …, 2018 - Springer
The Fréchet distance is a popular distance measure for curves which naturally lends itself to
fundamental computational tasks, such as clustering, nearest-neighbor searching, and …
fundamental computational tasks, such as clustering, nearest-neighbor searching, and …
A treehouse with custom windows: Minimum distortion embeddings into bounded treewidth graphs
Abstract We describe a (1+∊)-approximation algorithm for finding the minimum distortion
embedding of an n-point metric space X into the shortest path metric space of a weighted …
embedding of an n-point metric space X into the shortest path metric space of a weighted …
Learning lines with ordinal constraints
B Fan, DI Centurion, N Mohammadi, F Sgherzi… - arXiv preprint arXiv …, 2020 - arxiv.org
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 …
ordinal triple constraints. An ordinal constraint for a triple of points $(u, v, w) $ asserts that $| f …
Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
T Carpenter, FV Fomin, D Lokshtanov… - arXiv preprint arXiv …, 2017 - arxiv.org
We study the problem of finding a minimum-distortion embedding of the shortest path metric
of an unweighted graph into a" simpler" metric $ X $. Computing such an embedding …
of an unweighted graph into a" simpler" metric $ X $. Computing such an embedding …
Composition of nested embeddings with an application to outlier removal
S Chawla, K Sheridan - Proceedings of the 2024 Annual ACM-SIAM …, 2024 - SIAM
We study the design of embeddings into Euclidean space with outliers. Given a metric space
(X, d) and an integer k, the goal is to embed all but k points in X (called the “outliers”) into ℓ 2 …
(X, d) and an integer k, the goal is to embed all but k points in X (called the “outliers”) into ℓ 2 …
[PDF][PDF] Algorithms for metric learning via contrastive embeddings
D Ihara, N Mohammadi… - … Geometry (SoCG 2019), 2019 - drops.dagstuhl.de
We study the problem of supervised learning a metric space under discriminative
constraints. Given a universe X and sets S, D subset binom {X}{2} of similar and dissimilar …
constraints. Given a universe X and sets S, D subset binom {X}{2} of similar and dissimilar …
Approximation algorithms for low-distortion embeddings into low-dimensional spaces
We present several approximation algorithms for the problem of embedding metric spaces
into a line, and into the 2-dimensional plane. Among other results, we give an O(n) …
into a line, and into the 2-dimensional plane. Among other results, we give an O(n) …
[PDF][PDF] On clustering and related problems on curves under the Fréchet distance
A Krivošija - 2021 - eldorado.tu-dortmund.de
Sensor measurements can be represented as points in Rd. Ordered by the time-stamps of
these measurements, they yield a time series, that can be interpreted as a polygonal curve …
these measurements, they yield a time series, that can be interpreted as a polygonal curve …