Exact pseudopolynomial algorithms for a balanced 2-clustering problem

DOI10.1134/S1990478916030054zbMath1374.90323OpenAlexW2511842786MaRDI QIDQ2959183

A. V. Motkova, Alexander Kel'Manov

Publication date: 9 February 2017

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Euclidean spaceNP-hardnessbalanced clusteringfixed space dimensionexact pseudo-polynomial algorithminteger inputs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Elementary problems in Euclidean geometries (51M04)

Related Items (5)

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 ⋮ 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

Cites Work

• NP-hardness of some quadratic Euclidean 2-clustering problems
• NP-hardness of Euclidean sum-of-squares clustering
• A randomized approximation scheme for metric MAX-CUT
• 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
• On the complexity of some quadratic Euclidean 2-clustering problems
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• P-Complete Approximation Problems
• A 2-approximation polynomial algorithm for a clustering problem
• An FPTAS for a vector subset search problem
• Cluster Analysis and Mathematical Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Exact pseudopolynomial algorithms for a balanced 2-clustering problem