Pattern Matching in Doubling Spaces

Speaker: Prof. Antoine Vigneron
         UNIST
         South Korea

Title:  "Pattern Matching in Doubling Spaces"

Date:   Tuesday, October 3, 2023

Time:   10:30 am

Room:   Room 3523 (Conference Room, CSE Dept.)
        via lift 25/26, HKUST

Abstract:

We consider the problem of matching a metric space X of size k with a
subspace of a metric space of size n >= k, assuming that these two
spaces have constant doubling dimension. More precisely, given an input
parameter p>=1, the p-distortion problem is to find a one-to-one mapping
from X to Y that distorts distances by a factor at most p. We first show
by a reduction from k-clique that, in constant doubling dimension, this
problem is NP-hard and W[1]-hard. Then we provide a near-linear time
approximation algorithm for fixed k: Given an approximation ratio 0<e<1,
and a positive instance of the p-distortion problem, our algorithm returns
a solution to the (1+e)-distortion problem in near-linear time. We also
show how to extend these results to the minimum distortion problem, which
is an optimization version of the p-distortion problem where we allow
scaling. For doubling spaces, we prove the same hardness results, and for
fixed k, we give a (1+e)-approximation algorithm running in near-quadratic
time.


******************
Biography:

Antoine Vigneron is an Associate Professor of Computer Science and
Engineering at the Ulsan National Institute of Science and Technology
(UNIST) He graduated from the École Polytechnique (Paris), and he received
a PhD in Computer Science from the Hong Kong University of Science and
Technology. He previously worked at the National University of Singapore
(NUS), INRA (France) and KAUST (Saudi Arabia). His research field is
Computational Geometry.