REVIEW 3 major objections 6 minor 16 references
Fixed-sized clusters $k$-Means
T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Fixed-size k-means replaces nearest-centroid assignment with a Hungarian-algorithm step, enforcing exact cluster sizes while optimizing mean-square error.
desk verdict Correct algorithm, nice trick, but the 'more than 5000 points' claim is unsupported and likely false. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the assignment-problem reformulation of the assignment phase. Instead of assigning each point to its nearest centroid, the algorithm creates n cluster slots, partitions those slots into clusters of the required sizes, and treats the matching of points to slots as a linear assignment problem solved by the Hungarian algorithm. The edge weights are the squared Euclidean distances from each point to the centroid of the cluster containing the slot, and these weights are recomputed after every centroid update. This machinery is what enforces the exact-size constraint while keeping the objective aligned with mean-square error.
What would settle it
Run the algorithm on a small random dataset (say n = 20, k = 5 with equal cluster sizes) from many random initializations, logging the full point-to-cluster assignment at every iteration; if the same assignment appears in two non-consecutive iterations before centroids stabilize, the claimed finite termination is false.
Extended reading notes
Core claim
On its own terms, the paper's discovery is that the k-means assignment step can be replaced by an assignment problem without losing the algorithm's descent property. The paper constructs a bipartite graph with n data points on one side and n cluster slots on the other, groups the slots into clusters of prescribed sizes, and uses the Hungarian algorithm to find the minimum-cost bijection between points and slots, where the cost of assigning a point to a slot is the squared distance to that slot's cluster centroid. After reassignment, centroids are recomputed as the means of their assigned points. The paper argues that because both steps are individually optimal for mean-square error and the objective is bounded below, the procedure terminates at a locally optimal partitioning, applying a convergence result from constrained k-means to the exact-size case. It reports that the Hungarian assignment step runs in O($n^{3}$) time, which places the practical limit around 5,000 points, and illustrates the method on a seating-plan application.
Load-bearing premise
The whole convergence argument rests on the unproven assumption that Bradley et al.'s convergence proof for clusters with minimum-size constraints also applies when cluster sizes are fixed exactly; if that transfer fails, the algorithm could cycle instead of reaching a local optimum.
Editorial extensions
If this is right
- Balanced clustering with exactly equal cluster sizes becomes a direct instance of this algorithm, so applications that need equal-sized groups can use k-means-style iterations instead of bespoke balanced-clustering methods.
- The O(n^3) assignment phase makes the algorithm slower per iteration than standard k-means (O(k n)), but the paper's experiments indicate it is still practical up to roughly 5,000 points, a range where previous size-constrained methods were limited to a few hundred or 2,000 points.
- The seating-plan application shows a concrete use: pairwise compatibility distances can be embedded by multidimensional scaling and then partitioned into tables of fixed sizes while minimizing within-group squared distances.
- The convergence argument, if valid, means the algorithm inherits the local-optimality guarantee of k-means rather than merely producing a feasible partition.
Reading between the lines
- The paper does not prove that Bradley et al.'s convergence result for lower-bound size constraints transfers to exact-size constraints; a reader who wants certainty would need to check whether the finite-state argument survives the stricter constraint.
- If the convergence transfer fails, the algorithm could in principle cycle; this is testable by logging full assignments on small random datasets.
- The Hungarian-algorithm cost matrix has a special structure (n x n squared distances to k centroids with row and column constraints) that might allow faster-than-O(n^3) assignment in practice, though the paper does not explore this.
- For very large n, an auction algorithm or sparse assignment heuristic could extend the approach beyond 5,000 points at the cost of exactness, but the paper does not address this.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a modification of k-means in which each cluster has a prescribed, fixed size. In the assignment step, n data points are assigned to n cluster slots (with slots partitioned into k groups of given sizes) by solving a linear assignment problem with the Hungarian algorithm, using squared distances to the current centroids as costs. The update step recomputes centroids as the means of each cluster. The authors claim that this assignment is MSE-optimal for fixed centroids, that the algorithm converges to a locally optimal partition (citing Prop. 2.3 of Bradley et al. for constrained k-means), that the assignment step costs O(n^3), and that the algorithm is practical for datasets of more than 5000 points. The only experiment reported is a 22-person seating-plan application.
Significance. The algorithmic idea is simple and the per-iteration optimality of the Hungarian assignment for fixed centroids is correct; the paper therefore offers a clean baseline for exactly size-constrained k-means. The manuscript would be more valuable with a rigorous convergence proof for the exact-size case and, especially, experimental evidence for the '5000 points' scalability claim, which is central to the motivation and currently rests on a single n=22 example. If the claimed scalability is not demonstrated, the contribution shrinks to a small methodological note. The authors provide links to software, which is a strength for reproducibility.
major comments (3)
- [Abstract and Section 5] The claim that the algorithm 'enables clustering of datasets of size more than 5000 points' is unsupported: the only experiment (Section 4.1) uses n=22, and no runtime or memory measurements are reported anywhere. Under the stated O(n^3) assignment complexity with a dense n x n cost matrix, one Hungarian iteration at n=5000 entails on the order of 1.25e11 arithmetic operations, which is inconsistent with 'few seconds' per iteration. Since the motivation of the paper is to go beyond the 625- and 2000-point limits of prior work, the authors must provide wall-clock benchmarks as a function of n, or the scalability claim should be removed or substantially qualified.
- [Section 2 (convergence)] The convergence result is imported from Proposition 2.3 of Bradley et al., which is formulated for lower-bound constraints ('at least tau_h points'), while this paper imposes exact cluster sizes. The transfer is asserted, not proved. The authors should give a self-contained argument: show that the finite number of exact-size partitions, together with monotone non-increase of the MSE numerator across assignment and update steps and strict decrease in the update step unless a fixed point is reached, guarantees termination at a locally optimal partition. As written, the paper's central convergence guarantee depends on an unproved analogy.
- [Section 2] The term 'locally optimal' is used without definition in the exact-size setting. Bradley et al.'s Proposition 2.3 concerns their constrained objective and their notion of local optimality; the authors should state precisely what local optimality means here (for instance, no reassignment of a point from one cluster to another that preserves all cluster sizes strictly decreases the MSE), and prove that the algorithm's fixed points satisfy it.
minor comments (6)
- [Abstract] The phrase 'optimizes the mean square error, for given cluster sizes' could be read as claiming global optimality; recommend 'locally optimizes' or 'minimizes MSE at each iteration.'
- [Algorithm 1] The caption 'Fixed-sised clusters k-Means' contains a typo; it should be 'Fixed-sized.'
- [Section 2, Eq. (4)] The expression 'arg min_j c(j) >= a' is nonstandard; use a clearer definition such as j(a) = min{ j in {1,...,k} : c(j) >= a }.
- [Section 4.1] The text says '22 * 22 = 484 distances'; a 22x22 matrix has 484 entries, but the number of distinct pairwise distances is 231. Clarify whether the diagonal entries are counted as distances.
- [Throughout] There are minor typographical issues: 'Constrainedk-means' in Section 2 should be 'Constrained k-means', and 'f.eg.' in Section 5 should be 'e.g.'.
- [References] Reference [10] is listed as 'pre-published version'; please provide final publication details or a stable URL.
Circularity Check
No circularity found: the algorithm's MSE optimization is a direct property of its assignment and update steps, not a self-referential or fitted result.
full rationale
The paper's derivation chain is not circular. The algorithm is explicitly defined by an assignment step that solves a linear assignment problem with the Hungarian algorithm on squared distances to current centroids, and a centroid update step that recomputes cluster means; the MSE-decreasing property follows directly from these two optimization steps, not from any fitted parameter or self-referential definition. The convergence claim cites Bradley et al. (an external source) and asserts transfer to the fixed-size setting; even if that transfer is not proven, this is a correctness gap, not circularity. No fitted parameters are renamed as predictions; the only experiment is a 22-point seating plan, which is anecdotal, and the O(n^3) / 5000-point scalability statement is an unsupported practical claim, not a circular inference. Self-citations to the authors' earlier balanced-clustering papers appear only as background references and are not load-bearing. Hence no circular step meets the evidentiary standard required by the analysis instructions.
Assumptions & free parameters
assumptions (3)
- standard math The Hungarian algorithm returns an exact minimum-cost perfect matching for the n x n assignment problem.
- domain assumption Proposition 2.3 of Bradley et al. (Constrained k-means) remains valid when cluster sizes are exact rather than lower-bounded.
- standard math The MSE objective is nonincreasing under the alternating assignment and update steps.
Cite this review
Pith. "Pith review of Fixed-sized clusters $k$-Means." pith.science (2026). https://pith.science/paper/BJXVJT36
@misc{pith2026250116113,
author = {Pith},
title = {Pith review of: Fixed-sized clusters $k$-Means},
year = {2026},
howpublished = {\url{https://pith.science/paper/BJXVJT36}},
note = {Machine review of arXiv:2501.16113}
}
abstract
We present a $k$-means-based clustering algorithm, which optimizes the mean square error, for given cluster sizes. A straightforward application is balanced clustering, where the sizes of each cluster are equal. In the $k$-means assignment phase, the algorithm solves an assignment problem using the Hungarian algorithm. This makes the assignment phase time complexity $O(n^3)$. This enables clustering of datasets of size more than 5000 points.
Figures
Reference graph
Works this paper leans on
-
[1]
Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum- of-squares clustering. Mach. Learn. 75, 245–248 (2009)
work page 2009
-
[2]
In: SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Dis- crete algorithms
Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Dis- crete algorithms. pp. 1027–1035. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007)
work page 2007
-
[3]
Bradley, P.S., Bennett, K.P., Demiriz, A.: Constrained k-means clustering. Tech. rep., MSR-TR-2000-65, Microsoft Research (2000)
work page 2000
-
[4]
Burkhard, R., Dell’Amico, M., Martello, S.: Assignment Problems (Revised reprint). SIAM (2012)
work page 2012
-
[5]
Cox, T.F., Cox, M.A.A.: Multidimensional scaling. Chapman & Hall, London (1994)
work page 1994
-
[6]
Equitz, W.H.: A New Vector Quantization Clustering Algorithm. IEEE Trans. Acoust., Speech, Signal Processing 37, 1568–1575 (1989)
work page 1989
-
[7]
Fr¨ anti, P., Kivij¨ arvi, J.: Randomized local search algorithm for the clustering prob- lem. Pattern Anal. Appl. 3(4), 358–369 (2000) 7
work page 2000
-
[8]
Pat- tern Recognition 39(5), 761–765 (2006)
Fr¨ anti, P., Virmajoki, O.: Iterative shrinking method for clustering problems. Pat- tern Recognition 39(5), 761–765 (2006)
work page 2006
Show all 16 references
-
[9]
IEEE Trans
Fr¨ anti, P., Virmajoki, O., Hautam¨ aki, V.: Fast agglomerative clustering using a k- nearest neighbor graph. IEEE Trans. on Pattern Analysis and Machine Intelligence 28(11), 1875–1881 (2006)
2006
-
[10]
Ganganath, N., Cheng, C.T., Tse, C.K.: Data clustering with cluster size con- straints using a modified k-means algorithm, the pre-published version
-
[11]
Pattern Recognition 36, 451–461 (2003)
Likas, A., Vlassis, N., Verbeek, J.: The global k-means clustering algorithm. Pattern Recognition 36, 451–461 (2003)
2003
-
[12]
MacQueen, J.: Some methods of classification and analysis of multivariate observa- tions. Proc. 5th Berkeley Symp. Mathemat. Statist. Probability 1, 281–296 (1967)
1967
-
[13]
In: Joint Int
Malinen, M.I., Fr¨ anti, P.: Balanced k-means for clustering. In: Joint Int. Work- shop on Structural, Syntactic, and Statistical Pattern Recognition (S+SSPR 2014), LNCS 8621. Joensuu, Finland (2014)
2014
-
[14]
Applied Computing and Intelligence 3(1), 93–115 (May 2023)
Malinen, M.I., Fr¨ anti, P.: All-pairwise squared distances lead to more balanced clustering. Applied Computing and Intelligence 3(1), 93–115 (May 2023)
2023
-
[15]
In: Proceedings of the Seventeenth International Conference on Machine Learning
Pelleg, D., Moore, A.: X-means: Extending k-means with efficient estimation of the number of clusters. In: Proceedings of the Seventeenth International Conference on Machine Learning. pp. 727–734. Morgan Kaufmann, San Francisco (2000)
2000
-
[16]
Knowledge-Based Systems 23(8), 883–889 (2010)
Zhu, S., Wang, D., Li, T.: Data clustering with size constraints. Knowledge-Based Systems 23(8), 883–889 (2010)
2010
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.