Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters

DOI10.1134/S0081543816090066zbMath1362.68292OpenAlexW2582784988MaRDI QIDQ2396371

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

Publication date: 8 June 2017

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

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

zbMATH Keywords

Euclidean spacecluster analysisNP-hard problemPTAS

Mathematics Subject Classification ID

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

Related Items (8)

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem ⋮ 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 ⋮ Solving some vector subset problems by Voronoi diagrams ⋮ Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center ⋮ Complexity and approximation of finding the longest vector sum ⋮ Complexity and algorithms for finding a subset of vectors with the longest sum

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of a search for a subset of ``similar vectors
• NP-hardness of Euclidean sum-of-squares clustering
• A randomized algorithm for two-cluster partition of a set of vectors
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• 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
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• An approximation scheme for a problem of search for a vector subset

This page was built for publication: Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters