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. The k-center problem has recently been shown to be NP-hard, even in the case where k=1, i.e. the minimum enclosing ball under the Fr\'echet distance . We extend these results by showing that also the k-median problem is NP-hard for k=1. 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. Our result generalizes an earlier result by Bulteau et al. from 2018 for a variant of DTW that uses squared distances . Moreover, closing some gaps in the literature, we show positive results for a variant 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.
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.
R
The k-center problem has recently been shown to be NP-hard, even in the case where k=1, i.e. the minimum enclosing ball
Building upon recent hardness results for the minimum-enclosing-ball problem
R
. We extend these results by showing
, we show
R
k-median
1-median
R
for k=1.
.
R
Our result generalizes an
This yields an independent proof of an
R
. Moreover, closing some gaps in the literature, we show positive results for a variant
, where the new proof is both simpler and more general. On the positive side, we give approximation algorithms for problem variants