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

DOI10.1007/978-3-030-33394-2_16MaRDI QIDQ5214428zbMATH OpenOpenAlexFDO

Authors A. V. 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 spaceminimum sum-of-squares clusteringone-dimensional casepolynomial-time algorithmstrongly NP-hard problem

Mathematics Subject Classification ID

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

Recommendations

• The \((1 | 1)\)-centroid problem in the plane with distance constraints
• The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints
• A note on the p-center problem
• On the k-center problem with many centers
• On polynomial solvability of one quadratic Euclidean clustering problem on a line
• The Non-Uniform k -Center Problem
• The non-uniform k-center problem
• scientific article; zbMATH DE number 4209906
• Polynomial algorithms for restricted Euclidean p-centre problems
• Stochastic \(k\)-center and \(j\)-flat-center problems

Cites work

• A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
• A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train
• Cluster Analysis and Mathematical Programming
• scientific article; zbMATH DE number 3117956 (Why is no real title available?)
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• NP-hardness of Euclidean sum-of-squares clustering
• On the complexity of a search for a subset of ``similar vectors
• Posterior detection of a given number of identical subsequences in a quasi-periodic sequence
• The planar \(k\)-means problem is NP-hard

Cited in

(3)

• On polynomial solvability of one quadratic Euclidean clustering problem on a line
• Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem
• PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5214428)