Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem

DOI10.1134/S0965542519090112zbMath1494.68272OpenAlexW2980709110MaRDI QIDQ2284268

Vladimir Khandeev, Alexander Kel'Manov

Publication date: 14 January 2020

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0965542519090112

zbMATH Keywords

partitioningclusteringEuclidean spacepolynomial-time solvabilityone-dimensional caseminimum sum-of-squaresstrongly NP-hard problem

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• On the complexity of a search for a subset of ``similar vectors
• NP-hardness of Euclidean sum-of-squares clustering
• Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• Optimal quantization by matrix searching
• A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train
• Cluster Analysis and Mathematical Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem