Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem

DOI10.1134/S0965542516020111zbMath1362.68091MaRDI QIDQ2630015

Vladimir Khandeev, Alexander Kel'Manov

Publication date: 8 July 2016

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

zbMATH Keywords

partitionEuclidean spacecluster analysisNP-hardnessFPTASfixed space dimensionminimum of the sum of squares of distances

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

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 ⋮ Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters ⋮ A randomized algorithm for a sequence 2-clustering problem ⋮ Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster ⋮ 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

Uses Software

• HALCON
• PRMLT

Cites Work

• Unnamed Item
• 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
• Off-line detection of a quasi-periodically recurring fragment in a numerical sequence
• NP-hardness of Euclidean sum-of-squares clustering
• A randomized algorithm for two-cluster partition of a set of vectors
• Machine Learning
• 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 Introduction to Statistical Learning
• A 2-approximation polynomial algorithm for a clustering problem
• An FPTAS for a vector subset search problem
• Cluster Analysis and Mathematical Programming

This page was built for publication: Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem