Universal NP-Hardness of Clustering under General Utilities
Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperparameters, and initialisation. Existing theoretical results are largely objective-specific and do not explain these behaviours at a unifying level. We formalise the common optimisation core underlying diverse clustering paradigms by defining the Universal Clustering Problem (UCP): the maximisation of a polynomial-time computable partition utility over a finite metric space. We prove the NP-hardness of UCP via two independent polynomial-time reductions from graph colouring and from exact cover by 3-sets (X3C). By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental intractability. Our results provide a unified explanation for characteristic failure modes, such as local optima in alternating methods and greedy merge-order traps in hierarchical clustering. Finally, we show that clustering limitations reflect interacting computational and epistemic constraints, motivating a shift toward stability-aware objectives and interaction-driven formulations with explicit guarantees.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Value Under Ignorance in Universal Artificial Intelligence
We generalize the AIXI reinforcement learning agent to admit a wider class of utility functions. Assigning a utility to each possible interaction history forces us to confront the ambiguity that some hypotheses in the ag…
Reinforcement LearningOn Approximability of Clustering Problems Without Candidate Centers
The k-means objective is arguably the most widely-used cost function for modeling clustering tasks in a metric space. In practice and historically, k-means is thought of in a continuous setting, namely where the centers …
ClusteringMassively Parallel Algorithms and Hardness for Single-Linkage Clustering under $\ell_p$ Distances
We present first massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of n input d-dimensional vectors under Hamming, $\ell_1, \ell_2$ and $\ell_\infty$ d…
ClusteringTruthful Mechanisms for Matching and Clustering in an Ordinal World
We study truthful mechanisms for matching and related problems in a partial information setting, where the agents' true utilities are hidden, and the algorithm only has access to ordinal preference information. Our model…
ClusteringMaximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-like Graphs
Fractional hedonic games are coalition formation games where a player's utility is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which …