NP-hardness of Euclidean sum-of-squares clustering

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Machine-mediated learning

• Publication date

  2008-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10994-009-5103-0
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The hardness of k-means clustering

  2008cited by this paper
• On the Complexity of Minimum Sum-of-Squares Clustering

  2007influential reference
• k-means++: the advantages of careful seeding

  2007cited by this paper
• The Effectiveness of Lloyd-Type Methods for the k-Means Problem

  2006cited by this paper
• Online clustering of parallel data streams

  2006cited by this paper
• On the Complexity of Several Haplotyping Problems

  2005cited by this paper
• Clustering Large Graphs via the Singular Value Decomposition

  2004influential reference
• Cluster Analysis and Mathematical Programming

  2003cited by this paper
• Sparsest cuts and bottlenecks in graphs

  1990cited by this paper
• Some methods for classification and analysis of multivariate observations

  1967cited by this paper

• Universal NP-Hardness of Clustering under General Utilities

  2026cites this paper
• Integrating species distribution models (SDM) in spatially explicit GIS-tools to support nature-sensitive urban planning

  2026cites this paper
• A framework to evaluate the performance of Variational Quantum Algorithms

  2026cites this paper
• FastKPP: An exact accelerated <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e2115" altimg="si161.svg"> <mml:mi>k</mml:mi> </mml:math> -means <mml:math xmlns:mml="ht

  2026cites this paper
• Improved Minimum Sum-of-Squares Clustering (MSSC) Algorithm for Educational Big Data Recommendation Systems

  2026cites this paper
• The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It

  2026cites this paper
• Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation

  2026cites this paper
• RIS-Assisted Integrated Communication and Secret Key Generation in Quasi-Static Environments

  2026cites this paper
• PASS: Ambiguity Guided Subsets for Scalable Classical and Quantum Constrained Clustering

  2026cites this paper
• Cluster Overlap as Objective Function

  2025cites this paper
• Patterns, Causes, and Mortality Trends of Road Traffic Accidents in Hamedan Province, Iran: A Spatiotemporal Epidemiological Analysis (2011–2024)

  2025cites this paper
• Multi-convex Programming for Discrete Latent Factor Models Prototyping

  2025cites this paper
• Boosting Task Scheduling Data Locality with Low-latency, HW-accelerated Label Propagation

  2025cites this paper
• Fast Catalog Matching for Improved Posteriors via Constrained Clustering

  2025cites this paper
• Fixed-sized clusters k-Means

  2025cites this paper
• Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search

  2025cites this paper
• An Observation on Lloyd's k-Means Algorithm in High Dimensions

  2025cites this paper
• Buyer Beware: Understanding and Validating Distributional Assumptions of K-Means in College Student Typology Research

  2025cites this paper
• Dynamic order forecast sharing with dual shipping options under quantity flexibility contract

  2025cites this paper
• An Exact Solution Approach for Hierarchical Clustering

  2025cites this paper
• Kernel $k$-Medoids as General Vector Quantization

  2025cites this paper
• Strong bounds for large-scale Minimum Sum-of-Squares Clustering

  2025cites this paper
• Environmental Performance Assessment of a Decentralized Network of Recyclable Waste Sorting Facilities: Case Study in Montreal

  2025cites this paper
• The Karp Dataset

  2025cites this paper
• Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigation

  2025cites this paper
• The Structure of Extremal Bad Science Matrices

  2025cites this paper
• Evaluating Filter, Wrapper, and Embedded Feature Selection Approaches for Encrypted Video Traffic Classification

  2025cites this paper
• Souporcell3: Robust Demultiplexing for High-Donor Single-Cell RNA-seq Datasets

  2025cites this paper
• Exploring the use of a machine assisted goal and scope in a Life Cycle Studies to understand stakeholder interest and priorities

  2025cites this paper
• Inference of Transit Alighting From Automatic Boarding Count Data: A Double DQN Clustering

  2025cites this paper
• Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspective

  2025cites this paper
• Turning Big Data Into Tiny Data: Coresets for Unsupervised Learning Problems

  2025cites this paper
• MA-RAG: Automating Role Engineering for RESTful APIs with Multi-Head Attention and Retrieval-Augmented Generation

  2025cites this paper
• A Standardized Benchmark Set of Clustering Problem Instances for Comparing Black-Box Optimizers

  2025cites this paper
• Causal Clustering for Conditional Average Treatment Effects Estimation and Subgroup Discovery

  2025cites this paper
• Spectral Clustering for Community Extraction in Networks With Background Nodes

  2025cites this paper
• Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space

  2025cites this paper
• Federated k-Means over Networks

  2025cites this paper
• OrchardQuant‐3D: combining drone and LiDAR to perform scalable 3D phenotyping for characterising key canopy and floral traits in fruit orchards

  2025cites this paper
• Modified K-means Algorithm with Local Optimality Guarantees

  2025cites this paper
• First-improvement or best-improvement? An in-depth local search computational study to elucidate a dominance claim

  2025cites this paper
• A simple and computationally trivial estimator for grouped fixed effects models

  2025cites this paper
• Stochastic limited memory bundle algorithm for clustering in big data

  2025cites this paper
• Towards faster seeding for k-means++ via lower bound and triangle inequality

  2025cites this paper
• SoftBinReduce: data reduction for color quantization through soft binning

  2025cites this paper
• Binary k-Center with Missing Entries: Structure Leads to Tractability

  2025cites this paper
• A Scalable Global Optimization Algorithm For Constrained Clustering

  2025cites this paper
• A Recursive Spectral Clustering Algorithm for Intelligent Grouping in Dense Wireless Networks

  2025cites this paper
• Scalable Second-order Riemannian Optimization for K-means Clustering

  2025cites this paper
• Model Fusion via Neuron Interpolation

  2025cites this paper
• BiModalClust: Fused Data and Neighborhood Variation for Advanced K-Means Big Data Clustering

  2025cites this paper
• Accelerating the k-Means++ Algorithm by Using Geometric Information

  2024cites this paper
• The Fairness-Quality Trade-off in Clustering

  2024cites this paper
• Few-Shot Domain Adaptation for Named-Entity Recognition via Joint Constrained k-Means and Subspace Selection

  2024cites this paper
• On Approximability of ℓ22 Min-Sum Clustering

  2024cites this paper
• Testing for a difference in means of a single feature after clustering.

  2024cites this paper
• Distributed random swap: An efficient algorithm for minimum sum-of-squares clustering

  2024cites this paper
• STUN: Structured-Then-Unstructured Pruning for Scalable MoE Pruning

  2024cites this paper
• A comprehensive review of clustering techniques in artificial intelligence for knowledge discovery: Taxonomy, challenges, applications and future prospects

  2024cites this paper
• A nonparametric entropy-based measure of mass political polarization

  2024influential citation
• Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity

  2024cites this paper
• Parallel Iterative Mistake Minimization (IMM) clustering algorithm for shared-memory systems

  2024cites this paper
• On the Complexity of the Problem of Choice of Large Clusters

  2024cites this paper
• Dynamic Range Reduction via Branch-and-Bound

  2024cites this paper
• A Multi-Performance Reliability Evaluation Approach Based on the Surrogate Model with Cluster Mixing Weight

  2024cites this paper
• Performance of Hybrid Clustering-Classification Approach for Dual-Band System in a Mode-Locked Fiber Laser

  2024cites this paper
• Using low-discrepancy points for data compression in machine learning: an experimental comparison

  2024cites this paper
• Sub-One Quasi-Norm-Based k-Means Clustering Algorithm and Analyses

  2024cites this paper
• Optimal Location of Cellular Base Stations via Convex Optimization: An Analytical Framework and Numerical Algorithms

  2024cites this paper
• Second-order cone programming models for the unitary weighted Weber problem and for the minimum sum of the squares clustering problem

  2024cites this paper
• Annealed Multiple Choice Learning: Overcoming limitations of Winner-takes-all with annealing

  2024cites this paper
• Boosting K-means for Big Data by Fusing Data Streaming with Global Optimization

  2024cites this paper
• Imbalanced Data Clustering using Equilibrium K-Means

  2024cites this paper
• Planning Cost-Efficient FiWi Access Network With Joint Deployment of FWA and FTTH

  2024cites this paper
• A review on declarative approaches for constrained clustering

  2024cites this paper
• Deep Clustering Using the Soft Silhouette Score: Towards Compact and Well-Separated Clusters

  2024cites this paper
• On the power of linear programming for K-means clustering

  2024cites this paper
• Memetic Differential Evolution Methods for Semi-Supervised Clustering

  2024cites this paper
• On the Empirical Complexity of Reasoning and Planning in LLMs

  2024cites this paper
• DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods

  2024cites this paper
• FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy

  2024cites this paper
• Accelerated Sequential Data Clustering

  2024cites this paper
• Analysis of Quantum Machine Learning Algorithms in Noisy Channels for Classification Tasks in the IoT Extreme Environment

  2024cites this paper
• Sparse kernel k-means clustering

  2024cites this paper
• Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models

  2024cites this paper
• NUS: Noisy-Sample-Removed Undersampling Scheme for Imbalanced Classification and Application to Credit Card Fraud Detection

  2024cites this paper
• Implementação Paralela de Múltiplos K-Means em GPU

  2024cites this paper
• Fairness First Clustering: A Multi-Stage Approach for Mitigating Bias

  2023cites this paper
• Efficient Clustering of Visible Light Communications in VANET

  2023cites this paper
• An Effective and Efficient Algorithm for K-Means Clustering With New Formulation

  2023cites this paper
• Programmable Olfactory Computing

  2023cites this paper
• Uncertainty Informed Optimal Resource Allocation with Gaussian Process based Bayesian Inference

  2023cites this paper
• Time series clustering with random convolutional kernels

  2023cites this paper
• All-pairwise squared distances lead to more balanced clustering

  2023cites this paper
• Archetypal solution spaces for clustering gene expression datasets in identification of cancer subtypes

  2023cites this paper
• One-Pass Additive-Error Subset Selection for $$\ell _{p}$$ ℓ p Subspace Approximation and (k, p)-Clustering

  2023cites this paper
• Dim and Small Space-Target Detection and Centroid Positioning Based on Motion Feature Learning

  2023cites this paper
• Research on Defect Identification Method of Engine Lining

  2023cites this paper
• Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming

  2023cites this paper
• Forty years of color quantization: a modern, algorithmic survey

  2023cites this paper