Exact pseudo-polynomial algorithms for a balanced 2-clustering problem

DOI10.1134/S1990478916030054MaRDI QIDQ2959183zbMATH OpenOpenAlexFDO

Authors A. V. Motkova, A. V. 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

balanced clusteringEuclidean spaceexact pseudo-polynomial algorithmfixed space dimensioninteger inputsNP-hardness

Mathematics Subject Classification ID

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

Recommendations

• 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
• Exact algorithm for the one-dimensional quadratic Euclidean cardinality-weighted 2-clustering with given center problem
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• On the complexity of some quadratic Euclidean 2-clustering problems

Cites work

• A 2-approximation polynomial algorithm for a clustering problem
• A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
• A randomized algorithm for two-cluster partition of a set of vectors
• A randomized approximation scheme for metric MAX-CUT
• An approximation algorithm for a problem of cluster analysis
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• An FPTAS for a vector subset search problem
• Cluster Analysis and Mathematical Programming
• scientific article; zbMATH DE number 6004955 (Why is no real title available?)
• scientific article; zbMATH DE number 3584897 (Why is no real title available?)
• scientific article; zbMATH DE number 3617544 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• NP-hardness of Euclidean sum-of-squares clustering
• NP-hardness of some quadratic Euclidean 2-clustering problems
• On the complexity of some quadratic Euclidean 2-clustering problems
• P-Complete Approximation Problems
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• The problem of finding a subset of vectors with maximal total weight

Cited in

(11)

• Polynomial algorithms for nested univariate clustering
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Efficient solutions for weight-balanced partitioning problems
• Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster
• Exact algorithms for size constrained 2-clustering in the plane
• 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
• Exact algorithm for the one-dimensional quadratic Euclidean cardinality-weighted 2-clustering with given center problem
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence
• Exact algorithms for 2-clustering with size constraints in the Euclidean plane

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959183)