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

DOI10.1134/S0965542518050123zbMath1393.68176OpenAlexW2807997940WikidataQ129700851 ScholiaQ129700851MaRDI QIDQ1662580

Alexander Kel'Manov, Artem V. 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

partitioningEuclidean spaceNP-hardnessnorm of sum

Mathematics Subject Classification ID

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

Related Items (1)

Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space

Uses Software

• ElemStatLearn
• PRMLT

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of some Euclidean optimal summing problems
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• Data Mining
• The elements of statistical learning. Data mining, inference, and prediction

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