{"id":"7eafee2f-bd17-49dc-90f6-082927c1bdce","arxiv_id":"2501.16113","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A k-means variant that produces clusters of user-specified sizes by using the Hungarian algorithm to solve the assignment step.","lead":"Fixed-sized clusters k-means modifies the k-means clustering algorithm to enforce exact cluster sizes by solving the assignment step with the Hungarian algorithm. The method is claimed to handle datasets of around 5000 points, with a seating-plan application as a demonstration.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"O(n^3) complexity makes the 'more than 5000 points' scalability claim unsupported and likely false; convergence concern is secondary.","rationale":"The reader flagged the transfer of Bradley et al.'s convergence proof as the weakest assumption. On inspection, the convergence of the proposed algorithm does not depend on that transfer: the assignment step minimizes the objective for fixed centroids, the update step minimizes for fixed assignment, and the objective strictly decreases unless a fixed point is reached; since there are finitely many fixed-size partitions, termination is guaranteed. Thus that concern is not load-bearing. However, the paper's headline scalability claim is demonstrably shaky: an O(n^3) dense assignment step at n=5000 implies on the order of 10^11 operations per iteration, which is not 'practical' in any usual sense and is inconsistent with the only experiment (n=22). The paper provides no runtime measurements, no baselines, and no complexity analysis beyond the big-O. This makes the abstract's 'more than 5000 points' claim an internally inconsistent overstatement relative to the stated complexity. The algorithmic contribution may still be correct and useful for small n, but the practical scope is unverified. Therefore the reader's CONDITIONAL verdict remains appropriate; no verdict change is needed, but the scalability claim should be downgraded or experimentally justified.","tokens_in":130,"tokens_out":6054,"duration_ms":166514,"concrete_test":"Run the provided software on a synthetic 5000-point dataset (e.g., 10 Gaussian clusters) with k=10 equal sizes. Measure wall-clock time per iteration and total runtime until convergence. If total time exceeds 10 minutes on a standard workstation, the 'practical up to 5000 points' claim is not substantiated. Also compare runtime against constrained k-means (Bradley et al.) on n=2000 to check whether the proposed method is actually faster at the claimed scale.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The core assignment/update loop is mathematically sound: for fixed centroids, the Hungarian step globally minimizes MSE under exact size constraints, and the centroid update strictly decreases MSE unless a fixed point is reached; with finitely many size-feasible partitions, convergence follows directly without relying on Bradley et al.'s Proposition 2.3. The load-bearing weakness is the practical claim in the Abstract and Section 5 that the method 'enables clustering of datasets of size more than 5000 points.' The assignment step is O(n^3) using a dense n x n distance matrix; for n=5000 this is about 1.25e11 operations per iteration, and typical Hungarian implementations require far more than 'few seconds' per iteration. The only experiment is a 22-point seating plan, which gives no evidence at scale. If the O(n^3) scaling is taken literally, 5000-point clustering is likely slower than the 625- and 2000-point methods the paper criticizes, reversing the stated advantage. This scalability claim is central to the paper's motivation and is currently unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":3804,"tokens_out":5971,"duration_ms":52061,"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":[{"comment":"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":"Abstract and Section 5"},{"comment":"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":"Section 2 (convergence)"},{"comment":"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.","section":"Section 2"}],"minor_comments":[{"comment":"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.'","section":"Abstract"},{"comment":"The caption 'Fixed-sised clusters k-Means' contains a typo; it should be 'Fixed-sized.'","section":"Algorithm 1"},{"comment":"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":"Section 2, Eq. (4)"},{"comment":"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.","section":"Section 4.1"},{"comment":"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.'.","section":"Throughout"},{"comment":"Reference [10] is listed as 'pre-published version'; please provide final publication details or a stable URL.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is very short and the experimental section is a single anecdote. The core idea is publishable as a short paper if the convergence proof and scalability evidence are added. I would not accept it in current form. The '5000 points' estimate appears to be an extrapolation rather than a measured result; the authors should be asked to substantiate it or remove it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this is a clean, correct note about a simple idea: run k-means but replace the nearest-centroid assignment with an exact-size assignment solved by the Hungarian algorithm on the n x n distance matrix. The math checks out. For fixed centroids, the Hungarian step globally minimizes MSE subject to the size constraints; the centroid update minimizes MSE for the given partition; with finitely many feasible partitions, convergence to a local optimum follows directly. The paper actually does not need to borrow Bradley et al.'s convergence result; the standard finite-partition argument is enough, so that particular soft spot is easy to fix.\n\nWhat is genuinely useful: an exact, polynomial-time assignment step for fixed cluster sizes. The formulation via cluster slots is a natural modeling trick, and the seating-plan application is a nice concrete demo. The authors are honest that the algorithm is a local optimizer and compare the complexity with earlier size-constrained methods.\n\nThe real weakness is the scalability claim. The abstract and Section 5 say the method handles datasets 'more than 5000 points'. That number is not tested anywhere. The only experiment is 22 points. Hungarian on a dense 5000 x 5000 matrix costs around O(n^3) per iteration; in practice that is nowhere near 'few seconds' per iteration. The claim undercuts a method that compares favorably to the 625- and 2000-point ILP/upper-bound methods only if the complexity claim is taken literally. As written, the advertised advantage is unsupported and likely false.\n\nThere are also no baselines. A comparison against constrained or balanced k-means variants on a few moderate-size datasets would settle whether the extra Hungarian cost buys better MSE or better balance. The code is available, which is good, but the paper needs reproducible experiments.\n\nBottom line: this is a worthy short paper for the clustering community, provided the authors either remove the 5000-point claim or support it with actual runs, and add at least one baseline. I would send it to peer review with a request for major revision on the experimental side.\n\nRecommendation: engage with it, but insist on the experiments.","headline":"Correct algorithm, nice trick, but the 'more than 5000 points' claim is unsupported and likely false.","tokens_in":4325,"tokens_out":2124,"would_cite":false,"duration_ms":20064,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Fixed-size k-means replaces nearest-centroid assignment with a Hungarian-algorithm step, enforcing exact cluster sizes while optimizing mean-square error.","keywords":["clustering","fixed-sized clusters","size-constrained clustering","balanced clustering","assignment problem","Hungarian algorithm","k-means","mean square error"],"falsifier":"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.","tokens_in":3436,"feed_emoji":"📊","tokens_out":5492,"duration_ms":47304,"temperature":0.7,"pith_summary":"The paper proposes an extension of k-means in which each cluster is assigned a fixed, user-specified size and the assignment of points to clusters is solved exactly as a linear assignment problem with the Hungarian algorithm. The central claim is that this procedure optimizes the mean-square error subject to the size constraints, converges to a locally optimal partitioning, and remains practical for datasets up to roughly 5,000 points. The motivation is balanced clustering, where all clusters have equal size, and the paper demonstrates the method on a 22-person seating-plan problem. If the claims hold, size-constrained clustering becomes a drop-in replacement for ordinary k-means in applications that require balanced or quota-limited groups.","feed_headline":"Exact-size clusters via Hungarian assignment in k-means","feed_subtitle":"Balanced clustering with fixed group sizes becomes practical for datasets up to about 5,000 points.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes that Euclidean sum-of-squares clustering is NP-hard, motivating the k-means-style local-search approach the paper extends.","marker":"[1]"},{"why":"Supplies the convergence proposition (Proposition 2.3) that the paper transfers to exact-size clusters; the paper's termination claim depends on this transfer.","marker":"[3]"},{"why":"Provides the Hungarian algorithm used to solve the assignment problem in the assignment phase; the O(n^3) time complexity claim comes from this.","marker":"[4]"},{"why":"Defines the k-means algorithm whose assignment/update loop the paper modifies to enforce fixed cluster sizes.","marker":"[12]"},{"why":"Represents the prior size-constrained clustering approach with a 625-point limit, giving the scalability comparison for the paper's roughly 5,000-point claim.","marker":"[16]"},{"why":"Introduces the balanced-clustering objective that motivates exact equal-size cluster constraints.","marker":"[13]"}],"fun_headline_variants":["Hungarian assignment gives k-means exact-size clusters","Fixed-size k-means via Hungarian algorithm","k-means with controlled cluster sizes using Hungarian","Exact-size clustering: k-means meets Hungarian method","Practical exact-size k-means: Hungarian O(n^3) assignment"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hungarian assignment gives k-means exact-size clusters","Fixed-size k-means via Hungarian algorithm","k-means with controlled cluster sizes using Hungarian","Exact-size clustering: k-means meets Hungarian method","Practical exact-size k-means: Hungarian O(n^3) assignment"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000978,"raw_usage":{"total_tokens":4077,"prompt_tokens":791,"completion_tokens":3286,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":407,"completion_tokens_details":{"reasoning_tokens":3218}},"tokens_in":407,"tokens_out":3286,"duration_ms":23954,"temperature":1.0,"reasoning_tokens":3218,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T13:43:14.579147+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that Euclidean sum-of-squares clustering is NP-hard, motivating the k-means-style local-search approach the paper extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the convergence proposition (Proposition 2.3) that the paper transfers to exact-size clusters; the paper's termination claim depends on this transfer."},{"cited_title":"SIAM (2012)","cited_arxiv_id":null,"evidence_quote":"Provides the Hungarian algorithm used to solve the assignment problem in the assignment phase; the O(n^3) time complexity claim comes from this."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the k-means algorithm whose assignment/update loop the paper modifies to enforce fixed cluster sizes."},{"cited_title":"Knowledge-Based Systems 23(8), 883–889 (2010)","cited_arxiv_id":null,"evidence_quote":"Represents the prior size-constrained clustering approach with a 625-point limit, giving the scalability comparison for the paper's roughly 5,000-point claim."},{"cited_title":"In: Joint Int","cited_arxiv_id":null,"evidence_quote":"Introduces the balanced-clustering objective that motivates exact equal-size cluster constraints."}],"review_version":1}