On the Hardness of Computing an Average Curve.

DOI10.4230/LIPICS.SWAT.2020.19MaRDI QIDQ6059183zbMATH OpenOpenAlexFDO

Authors Kevin Buchin, Anne Driemel, Martijn Struijs

Publication date 2 November 2023

Full work available at URL https://arxiv.org/abs/1902.08053

zbMATH Keywords

algorithmsapproximationclusteringcurveshardness

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We study the complexity of clustering curves under $k$-median and $k$-center objectives in the metric space of the Fr'echet distance and related distance measures. Building upon recent hardness results for the minimum-enclosing-ball problem under the Fr'echet 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'echet 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 $ell$ under the discrete Fr'echet distance. In particular, for fixed $k,ell$ and $varepsilon$, we give $(1+varepsilon)$-approximation algorithms for the $(k,ell)$-median and $(k,ell)$-center objectives and a polynomial-time exact algorithm for the $(k,ell)$-center objective.

Cited in

(7)

• On the hardness of finding subsets with equal average
• Tight hardness results for consensus problems on circular strings and time series
• Approximating ( k,ℓ )-Median Clustering for Polygonal Curves
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• Approximating length-restricted means under dynamic time warping
• Fast approximations and coresets for (k,)-median under dynamic time warping
• Random projections for curves in high dimensions

This page was built for publication: On the Hardness of Computing an Average Curve.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6059183)