The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension

DOI10.1007/978-3-030-33394-2_16zbMath1429.90096OpenAlexW2982434099MaRDI QIDQ5214428

Alexander Kel'Manov, Vladimir Khandeev

Publication date: 7 February 2020

Published in: Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-33394-2_16

zbMATH Keywords

Euclidean spacepolynomial-time algorithmone-dimensional caseminimum sum-of-squares clusteringstrongly NP-hard problem

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Dynamic programming (90C39)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The planar \(k\)-means problem is NP-hard
• 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
• A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train
• Cluster Analysis and Mathematical Programming

This page was built for publication: The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension