License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.19
URN: urn:nbn:de:0030-drops-122662
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12266/
Go to the corresponding LIPIcs Volume Portal

Buchin, Kevin ; Driemel, Anne ; Struijs, Martijn

On the Hardness of Computing an Average Curve

pdf-format:
LIPIcs-SWAT-2020-19.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{buchin_et_al:LIPIcs:2020:12266,
  author =	{Kevin Buchin and Anne Driemel and Martijn Struijs},
  title =	{{On the Hardness of Computing an Average Curve}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12266},
  URN =		{urn:nbn:de:0030-drops-122662},
  doi =		{10.4230/LIPIcs.SWAT.2020.19},
  annote =	{Keywords: Curves, Clustering, Algorithms, Hardness, Approximation}
}

Keywords: Curves, Clustering, Algorithms, Hardness, Approximation
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI