On polynomial solvability of one quadratic Euclidean clustering problem on a line

DOI10.1134/S1064562419040057MaRDI QIDQ2279767zbMATH OpenOpenAlexWikidataFDO

Authors A. V. Kel'manov, Vladimir Khandeev

Publication date 13 December 2019

Published in Doklady Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem
• Exact algorithm for the one-dimensional quadratic Euclidean cardinality-weighted 2-clustering with given center problem
• The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension
• On the complexity of some quadratic Euclidean 2-clustering problems
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem

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
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• 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

Cited in

(6)

• Polynomial algorithms for nested univariate clustering
• Minimum sum of squares clustering in a low dimensional space
• Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem
• scientific article; zbMATH DE number 6004969 (Why is no real title available?)
• Exact algorithm for the one-dimensional quadratic Euclidean cardinality-weighted 2-clustering with given center problem
• The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension

This page was built for publication: On polynomial solvability of one quadratic Euclidean clustering problem on a line

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