论文标题
K-Median在离散的Fréchet和Hausdorff距离下聚类
k-Median clustering under discrete Fréchet and Hausdorff distances
论文作者
论文摘要
我们给出了第一个接近线性的时间$（1+ \ eps）$ - $ k $ -MMEDIAIN的近似算法 - 在离散的Fréchet距离下多边形轨迹的聚类，以及第一个多项式时间$（1+ \ EPS）$ - 近似值算法的$ k $ - 近似级别的距离 - 中间级别的距离，该集群的集群集群群集群集群集群集群集群集群集群集，尺寸和$ k $由常数界定。主要技术是解决聚类问题的一般框架，其中群集中心仅限于\ emph {simple}公制空间。我们精确地表征了群集中心的简单度量空间的条件，这些条件允许$ K $ -Median问题更快的$（1+ \ EPS）$ - 近似值。我们还表明，Hausdorff距离下的$ K $ -Median问题为\ textsc {np-hard}。
We give the first near-linear time $(1+\eps)$-approximation algorithm for $k$-median clustering of polygonal trajectories under the discrete Fréchet distance, and the first polynomial time $(1+\eps)$-approximation algorithm for $k$-median clustering of finite point sets under the Hausdorff distance, provided the cluster centers, ambient dimension, and $k$ are bounded by a constant. The main technique is a general framework for solving clustering problems where the cluster centers are restricted to come from a \emph{simpler} metric space. We precisely characterize conditions on the simpler metric space of the cluster centers that allow faster $(1+\eps)$-approximations for the $k$-median problem. We also show that the $k$-median problem under Hausdorff distance is \textsc{NP-Hard}.
