Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems

DOI10.15372/SJNM20190201MaRDI QIDQ5043014zbMATH OpenOpenAlexFDO

Authors A. V. Panasenko, A. V. Kel'manov, Vladimir Khandeev

Publication date 26 October 2022

Published in Сибирский журнал вычислительной математики (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/sjvm705

zbMATH Keywords

exact algorithmNP-hardnessEuclidean spacelargest subset2-clusteringpseudopolynomial-time solvability

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational aspects of data analysis and big data (68T09) Applications of mathematical programming (90C90) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• scientific article; zbMATH DE number 6004969 (Why is no real title available?)
• scientific article; zbMATH DE number 3117956 (Why is no real title available?)
• scientific article; zbMATH DE number 3617544 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• A 2-approximation polynomial algorithm for a clustering problem
• A fully polynomial-time approximation scheme for a special case of a balanced 2-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 exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• An introduction to statistical learning. With applications in R
• Cluster Analysis and Mathematical Programming
• Cluster analysis and mathematical programming
• Clustering large graphs via the singular value decomposition
• Complexity of the weighted max-cut in Euclidean space
• Data mining. The textbook
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• Minimum sum of squares clustering in a low dimensional space
• NP-hardness of Euclidean sum-of-squares clustering
• NP-hardness of some quadratic Euclidean 2-clustering problems
• NP-hardness of the Euclidean Max-Cut problem
• On the complexity of a search for a subset of ``similar vectors
• On the complexity of some quadratic Euclidean 2-clustering problems
• P-Complete Approximation Problems
• Pattern recognition and machine learning.
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Solving some vector subset problems by Voronoi diagrams
• The planar \(k\)-means problem is NP-hard
• The problem of finding a subset of vectors with maximal total weight

Cited in

(3)

• Constant-factor approximation algorithms for some maximin multi-clustering problems
• Exact algorithms for size constrained 2-clustering in the plane
• An exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem

This page was built for publication: Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems

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