Vi studerar komplexiteten i klusterkurvor under k-median och k-center mål i det metriska utrymmet för Fréchet avstånd och relaterade avstånd åtgärder. K-centerproblemet har nyligen visat sig vara NP-hard, även i fallet där k = 1, dvs. Den minsta omslutningskulan under Fréchet-avståndet. Vi utökar dessa resultat genom att visa att även k-median problemet är NP-hård för k = 1. Dessutom visar vi att 1-median problemet är W[1]-hård med antalet kurvor som parameter. Vi visar detta under den diskreta och kontinuerliga Fréchet och Dynamic Time Warping (DTW) avstånd. Vårt resultat generaliserar ett tidigare resultat av Bulteau et al. från och med 2018 för en variant av DTW som använder kvadratavstånd. Dessutom, att stänga vissa luckor i litteraturen, visar vi positiva resultat för en variant där mittkurvan kan ha komplexitet som mest under diskret Fréchet avstånd. Särskilt för fasta k, och ε, ger vi (1 + ε)-tillnärmning algoritmer för (k, )-median och (k, )-center mål och en polynom-tid exakt algoritm för (k, )-center mål.  ACM Subject Classification Clustering är ett viktigt verktyg i dataanalys, som används för att dela upp data i grupper av liknande objekt. Deras olikhet är ofta baserad på avståndet mellan punkter i Euclidean rymden. Skillnaderna i (polygonala) kurvor mäts dock mer exakt genom specialiserade åtgärder: Dynamic Time Warping (DTW) [18], kontinuerlig och diskret Fréchet avstånd [1, 8]. Vi fokuserar på centroidbaserad klusterbildning, där varje kluster har en mittkurva och kvaliteten på klustret baseras på likheten mellan centrum och elementen inuti klustret. I synnerhet, med tanke på ett avståndsmått δ, tar vi hänsyn till följande problem: Problem 1 (k-median för kurvor med avstånd δ). Eftersom en uppsättning G = {g 1,. .., g m } av polygonala kurvor, hitta en uppsättning C = {c 1,. .. c k } av polygonala kurvor som minimerar problem 2 (k-centrum för kurvor med avstånd δ). Eftersom en uppsättning G = {g 1,. .., g m } av polygonala kurvor, hitta en uppsättning C = {c 1,. .. c k } av polygonala kurvor som minimerar max K-median problemet för allmänna metriska utrymmen är väl studerad, ofta i samband med den närbesläktade anläggningen plats problem [14, 13, 15]. Vanligtvis, de anser vad vi kommer att kalla den diskreta k-median problem, där centra måste väljas från uppsättningen av inmatningspunkter. I denna uppsats är vi intresserade av det okonstruerade k-medianproblemet, där centra kan vara någon del av det metriska utrymmet. Ofta skriver vi helt enkelt k-median problem arXiv:1902.08053v1 [cs.CG]
Ännu mer nyligen visade REF att k-medianproblemet också är NP- hårt för k = 1 och förbättrades på de ovannämnda (1 + ε) - approximationer.
On the hardness of computing an average curve
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}