文章基本信息

标题：On the Hardness of Computing an Average Curve
本地全文：下载
作者：Kevin Buchin ; Anne Driemel ; Martijn Struijs 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：19:1-19:19
DOI：10.4230/LIPIcs.SWAT.2020.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the complexity of clustering curves under k-median and k-center objectives in the metric space of the FrÃ©chet distance and related distance measures. Building upon recent hardness results for the minimum-enclosing-ball problem under the FrÃ©chet distance, we show that also the 1-median problem is NP-hard. Furthermore, we show that the 1-median problem is W[1]-hard with the number of curves as parameter. We show this under the discrete and continuous FrÃ©chet and Dynamic Time Warping (DTW) distance. This yields an independent proof of an earlier result by Bulteau et al. from 2018 for a variant of DTW that uses squared distances, where the new proof is both simpler and more general. On the positive side, we give approximation algorithms for problem variants where the center curve may have complexity at most ð" under the discrete FrÃ©chet distance. In particular, for fixed k, ð" and Îµ, we give (1+Îµ)-approximation algorithms for the (k,ð")-median and (k,ð")-center objectives and a polynomial-time exact algorithm for the (k,ð")-center objective.
关键词：Curves; Clustering; Algorithms; Hardness; Approximation