Tight Hardness Results for Consensus Problems on Circular Strings and Time Series

DOI10.1137/19M1255781zbMath1462.68065arXiv1804.02854OpenAlexW3081054482MaRDI QIDQ5128513

Rolf Niedermeier, Vincent Froese, Laurent Bulteau

Publication date: 27 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsdynamic time warpingparameterized complexityexponential time hypothesistime series averagingcircular string alignmentfine-grained complexity and reductions

Mathematics Subject Classification ID

Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

The complexity of binary matrix completion under diameter constraints ⋮ An average-compress algorithm for the sample mean problem under dynamic time warping ⋮ Approximating length-restricted means under dynamic time warping

Cites Work

• Unnamed Item
• Unnamed Item
• A global averaging method for dynamic time warping, with applications to clustering
• On covering problems of codes
• Summarizing a set of time series by averaging: from Steiner sequence to compact multiple alignment
• On the parameterized intractability of motif search problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Finding similar regions in many sequences
• Finding consensus and optimal alignment of circular strings
• Exact mean computation in dynamic time warping spaces
• Tight lower bounds for certain parameterized NP-hard problems
• Accurate and Efficient Methods to Improve Multiple Circular Sequence Alignment
• On the closest string and substring problems
• Closest Substring Problems with Small Distances
• Dynamic Time Warping and Geometric Edit Distance
• Fast and Accurate Time-Series Clustering
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• On the Hardness of Computing an Average Curve.

This page was built for publication: Tight Hardness Results for Consensus Problems on Circular Strings and Time Series