2026-07-25T23:20:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23214 2025-10-02T12:43:16Z ddc:004 open_access

On Approximability of 𝓁₂² Min-Sum Clustering Karthik C. S. Lee, Euiwoong Rabani, Yuval Schwiegelshohn, Chris Zhou, Samson Clustering hardness of approximation polynomial-time approximation schemes learning-augmented algorithms The 𝓁₂² min-sum k-clustering problem is to partition an input set into clusters C_1,…,C_k to minimize ∑_{i=1}^k ∑_{p,q ∈ C_i} ‖p-q‖₂². Although 𝓁₂² min-sum k-clustering is NP-hard, it is not known whether it is NP-hard to approximate 𝓁₂² min-sum k-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the 𝓁₂² min-sum k-clustering problem. We show that it is NP-hard to approximate the objective to a factor better than 1.056 and moreover, assuming a balanced variant of the Johnson Coverage Hypothesis, it is NP-hard to approximate the objective to a factor better than 1.327. We then complement our hardness result by giving a fast PTAS for 𝓁₂² min-sum k-clustering. Specifically, our algorithm runs in time O(n^{1+o(1)}d⋅ 2^{(k/ε)^O(1)}), which is the first nearly linear time algorithm for this problem. We also consider a learning-augmented setting, where the algorithm has access to an oracle that outputs a label i ∈ [k] for input point, thereby implicitly partitioning the input dataset into k clusters that induce an approximately optimal solution, up to some amount of adversarial error α ∈ [0,1/2). We give a polynomial-time algorithm that outputs a (1+γα)/(1-α)²-approximation to 𝓁₂² min-sum k-clustering, for a fixed constant γ > 0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karthik C. S. and Euiwoong Lee and Yuval Rabani and Chris Schwiegelshohn and Samson Zhou 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.62 urn:nbn:de:0030-drops-232142 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.62 eng https://creativecommons.org/licenses/by/4.0/legalcode