2026-07-23T00:29:22Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:18588 2024-03-06T11:02:12Z ddc:004 open_access
On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric Holznigenkemper, Jana Komusiewicz, Christian Morawietz, Nils Seeger, Bernhard Parameterized Complexity Median String Time Series ETH We initiate a study of the complexity of MSM-Median, the problem of computing a median of a set of k real-valued time series under the move-split-merge distance. This distance measure is based on three operations: moves, which may shift a data point in a time series; splits, which replace one data point in a time series by two consecutive data points of the same value; and merges, which replace two consecutive data points of equal value by a single data point of the same value. The cost of a move operation is the difference of the data point value before and after the operation, the cost of split and merge operations is defined via a given constant c. Our main results are as follows. First, we show that MSM-Median is NP-hard and W[1]-hard with respect to k for time series with at most three distinct values. Under the Exponential Time Hypothesis (ETH) our reduction implies that a previous dynamic programming algorithm with running time |I|^π’ͺ(k) [Holznigenkemper et al., Data Min. Knowl. Discov. '23] is essentially optimal. Here, |I| denotes the total input size. Second, we show that MSM-Median can be solved in 2^π’ͺ(d/c)β‹…|I|^π’ͺ(1) time where d is the total distance of the median to the input time series. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Jana Holznigenkemper and Christian Komusiewicz and Nils Morawietz and Bernhard Seeger 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.54 urn:nbn:de:0030-drops-185889 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.54 eng https://creativecommons.org/licenses/by/4.0/legalcode