Exact algorithms for size constrained 2-clustering in the plane

DOI10.1016/J.TCS.2015.10.005MaRDI QIDQ288798zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jianyi Lin, Massimiliano Goldwurm, Alberto Bertoni

Publication date 27 May 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.10.005

zbMATH Keywords

Euclidean normconvex hull\(k\)-setalgorithms for clusteringcluster size constraintsManhattan norm

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Exact algorithms for 2-clustering with size constraints in the Euclidean plane
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• Exact and approximation algorithms for clustering
• A 2-approximation algorithm for the graph 2-clustering problem
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• scientific article; zbMATH DE number 1303609
• 2-approximation algorithms for two graph clustering problems
• A 2-approximation polynomial algorithm for a clustering problem
• Efficient approximation schemes for uniform-cost clustering problems in planar graphs
• On the complexity of clustering with relaxed size constraints in fixed dimension

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• scientific article; zbMATH DE number 3407703 (Why is no real title available?)
• Exact algorithms for 2-clustering with size constraints in the Euclidean plane
• General equation for taxicab conics and their classification
• Improved bounds for planar \(k\)-sets and related problems
• Integer Programming and the Theory of Grouping
• Introduction to algorithms
• Maintenance of configurations in the plane
• Minimum sum of squares clustering in a low dimensional space
• NP-hardness of Euclidean sum-of-squares clustering
• Norm statistics and the complexity of clustering problems
• Pattern recognition and machine learning.
• Size constrained distance clustering: separation properties and some complexity results
• The planar \(k\)-means problem is NP-hard
• \(k\)-means requires exponentially many iterations even in the plane

Cited in

(8)

• An exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem
• On the Complexity of Clustering with Relaxed Size Constraints
• A finite exact algorithm for epsilon-core membership in two dimensions
• On the complexity of clustering with relaxed size constraints in fixed dimension
• Exact algorithms for 2-clustering with size constraints in the Euclidean plane
• Geometric clustering in normed planes
• Some clustering algorithms in normed planes
• NP-hardness of \(m\)-dimensional weighted matching problems

Describes a project that uses

Uses Software

• ElemStatLearn
• PRMLT

This page was built for publication: Exact algorithms for size constrained 2-clustering in the plane

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