Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster

DOI10.1134/S0081543818090146zbMath1486.68256OpenAlexW2921377059MaRDI QIDQ2424187

Alexander Kel'Manov, V. V. Shenmaier, A. V. Motkova

Publication date: 24 June 2019

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

clusteringEuclidean spaceNP-hardnessPTASFPTAS

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

Uses Software

• ElemStatLearn
• ISLR
• PRMLT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-hardness of some quadratic Euclidean 2-clustering problems
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• A randomized algorithm for two-cluster partition of a set of vectors
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• On the complexity of some quadratic Euclidean 2-clustering problems
• Exact pseudopolynomial algorithms for a balanced 2-clustering problem
• Solving some vector subset problems by Voronoi diagrams
• Complexity of certain problems of searching for subsets of vectors and cluster analysis
• A Fully Polynomial-Time Approximation Scheme for a Special Case of a Balanced 2-Clustering Problem
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• Finding k points with minimum diameter and related problems
• An Introduction to Statistical Learning
• Data Mining
• An approximation scheme for a problem of search for a vector subset
• An FPTAS for a vector subset search problem

This page was built for publication: Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster