An LP-based \(k\)-means algorithm for balancing weighted point sets

DOI10.1016/j.ejor.2017.04.054zbMath1381.62154arXiv1308.4004OpenAlexW2608972419WikidataQ60242757 ScholiaQ60242757MaRDI QIDQ1694906

Peter Gritzmann, Andreas Brieden, Steffen Borgwardt

Publication date: 6 February 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.4004

zbMATH Keywords

linear programmingclusteringdata mining\(k\)-meansweight-balancing

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational learning theory (68Q32) Applications of mathematical programming (90C90) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Related Items (6)

Improved parameterized approximation for balanced \(k\)-median ⋮ Power diagram detection with applications to information elicitation ⋮ Constrained clustering via diagrams: a unified theory and its application to electoral district design ⋮ Turning Grain Maps into Diagrams ⋮ Faster balanced clusterings in high dimension ⋮ On parameterized approximation algorithms for balanced clustering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The planar \(k\)-means problem is NP-hard
• Geometric clustering for the consolidation of farmland and woodland
• Improved and simplified inapproximability for \(k\)-means
• \(k\)-means requires exponentially many iterations even in the plane
• On clustering bodies: geometry and polyhedral approximation
• NP-hardness of Euclidean sum-of-squares clustering
• Optimal partitions having disjoint convex and conic hulls
• Multicategory classification by support vector machines
• Minkowski-type theorems and least-squares clustering
• Constrained minimum-\(k\)-star clustering and its application to the consolidation of farmland
• The Vector Partition Problem for Convex Objective Functions
• Partitions
• On Optimal Weighted Balanced Clusterings: Gravity Bodies and Power Diagrams
• 10.1162/15324430260185628
• Constrained Clustering
• The Complexity of the k-means Method
• A Polynomial Time Algorithm for Shaped Partition Problems
• Power Diagrams: Properties, Algorithms and Applications
• Least squares quantization in PCM
• k-Means Has Polynomial Smoothed Complexity
• Smoothed Analysis of the k-Means Method
• Lower Bounds for Approximation by Nonlinear Manifolds

This page was built for publication: An LP-based \(k\)-means algorithm for balancing weighted point sets