论文标题
在双倍空间中匹配的图案匹配
Pattern Matching in Doubling Spaces
论文作者
论文摘要
我们认为，与公制空间$（y，d_y）$的子空间相匹配的度量空间$（x，d_x）$的尺寸$ n \ geq k $的子空间，假设这两个空间具有恒定的尺寸dimension $δ$。更确切地说，给定输入参数$ρ\ geq 1 $，$ρ$ - 差异问题是找到一个从$ x $到$ y $的一对一映射，最多以$ρ$扭曲了一个因子。我们首先以$ k $ -clique的减少来显示，在二倍尺寸$ \ log_2 3 $中，此问题是np-hard和w [1] -hard。然后，我们提供固定$ k $的接近线性时间近似算法：给定近似值$ 0 <\ varepsilon \ leq 1 $，以及$ρ$ - distortial问题的积极实例，我们的算法返回到$（1+ \ varepsilon）的解决方案中的时间（1+ \ varepsilon）ρ$ - ρ$ -Disteptionρ$ - ρ$ - ρ$ - ρ$ -DISTERTIC $（ρ/\ varepsilon）^{o（1）} n \ log n $。我们还展示了如何将这些结果扩展到两倍的空间中的最小失真问题：我们证明了相同的硬度结果，对于固定的$ k $，我们给出了$（1+ \ varepsilon）$ - 近似算法，以时间$ $ $（$ dist $（$ dist $（x，x，y）/\ varepsilon）/\ varepsilon）^$（1） $ x $和$ y $之间的失真。
We consider the problem of matching a metric space $(X,d_X)$ of size $k$ with a subspace of a metric space $(Y,d_Y)$ of size $n \geq k$, assuming that these two spaces have constant doubling dimension $δ$. More precisely, given an input parameter $ρ\geq 1$, the $ρ$-distortion problem is to find a one-to-one mapping from $X$ to $Y$ that distorts distances by a factor at most $ρ$. We first show by a reduction from $k$-clique that, in doubling dimension $\log_2 3$, 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<\varepsilon\leq 1$, and a positive instance of the $ρ$-distortion problem, our algorithm returns a solution to the $(1+\varepsilon)ρ$-distortion problem in time $(ρ/\varepsilon)^{O(1)}n \log n$. We also show how to extend these results to the minimum distortion problem in doubling spaces: We prove the same hardness results, and for fixed $k$, we give a $(1+\varepsilon)$-approximation algorithm running in time $($dist$(X,Y)/\varepsilon)^{O(1)}n^2\log n$, where dist$(X,Y)$ denotes the minimum distortion between $X$ and $Y$.
