Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

DOI10.1134/S0965542519050099zbMath1423.68597OpenAlexW2949705213MaRDI QIDQ2332640

Vladimir Khandeev, Alexander Kel'Manov, A. V. Panasenko

Publication date: 4 November 2019

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

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

zbMATH Keywords

partitioningapproximation algorithmEuclidean spaceNP-hardnessminimum sum-of-squared distances

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Uses Software

• PRMLT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-hardness of some quadratic Euclidean 2-clustering problems
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• A randomized algorithm for two-cluster partition of a set of vectors
• Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster
• On the complexity of some quadratic Euclidean 2-clustering problems
• Solving some vector subset problems by Voronoi diagrams
• A Fully Polynomial-Time Approximation Scheme for a Special Case of a Balanced 2-Clustering Problem
• Finding k points with minimum diameter and related problems
• P-Complete Approximation Problems
• An Introduction to Statistical Learning
• Robust Methods for Data Reduction
• Data Mining
• An approximation scheme for a problem of search for a vector subset
• An FPTAS for a vector subset search problem