NP-hardness of some Euclidean problems of partitioning a finite set of points

DOI10.1134/S0965542518050123zbMATHOpenAlexWikidataMaRDI QIDQ1662580FDO

Authors A. V. Kel'manov, Artem Pyatkin

Publication date 20 August 2018

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

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

zbMATH Keywords

NP-hardnessEuclidean spacepartitioningnorm of sum

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the complexity of some Euclidean problems of partitioning a finite set of points
• NP-hardness of some quadratic Euclidean 2-clustering problems
• NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters
• On the complexity of some quadratic Euclidean partition problems into balanced clusters
• Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• Data mining. The textbook
• On the complexity of some Euclidean optimal summing problems
• Pattern recognition and machine learning.
• The elements of statistical learning. Data mining, inference, and prediction

Cited in

(12)

• scientific article; zbMATH DE number 3921982 (Why is no real title available?)
• NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters
• Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space
• NP-hardness of some quadratic Euclidean 2-clustering problems
• On the complexity of some quadratic Euclidean partition problems into balanced clusters
• Complexity of some problems of quadratic partitioning of a finite set of points in Euclidean space into balanced clusters
• NP-hardness of some max-min clustering problems
• On complexity of some problems of cluster analysis of vector sequences
• On the complexity of some Euclidean problems of partitioning a finite set of points
• On the complexity of some Euclidean optimal summing problems
• NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes
• Polynomial-time solvability of the one-dimensional case of an NP-hard clustering problem

Describes a project that uses

Uses Software

• ElemStatLearn
• PRMLT

This page was built for publication: NP-hardness of some Euclidean problems of partitioning a finite set of points

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