NP-hardness of some quadratic Euclidean 2-clustering problems

DOI10.1134/S1064562415050233zbMath1335.68096OpenAlexW2192802981MaRDI QIDQ906118

Artem V. Pyatkin, Alexander Kel'Manov

Publication date: 29 January 2016

Published in: Doklady Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster ⋮ Exact pseudopolynomial algorithms for a balanced 2-clustering problem ⋮ 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence ⋮ Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center ⋮ Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

Cites Work

• Unnamed Item
• Unnamed Item
• NP-hardness of the Euclidean Max-Cut problem
• On the complexity of a search for a subset of ``similar vectors
• NP-hardness of Euclidean sum-of-squares clustering
• A randomized approximation scheme for metric MAX-CUT
• On the complexity of some cluster analysis problems
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• On the complexity of some data analysis problems
• P-Complete Approximation Problems
• Complexity of the weighted max-cut in Euclidean space

This page was built for publication: NP-hardness of some quadratic Euclidean 2-clustering problems