{"id":"3fa1ed38-22a2-4c27-a7e6-1c3c4b4f7da1","arxiv_id":"2412.10923","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper defines a linear program that detects outliers and, together with a rounding algorithm, gives constant-factor approximations for individually fair k-means and k-median clustering with outliers.","lead":"A new algorithm finds k cluster centers while guaranteeing each non-outlier point is close to a center, even when the data contains outliers. It is the first constant-factor approximation for individually fair k-means and k-median clustering with outliers, though a key bound on how many points it labels as outliers is missing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"OutRound can label more than m points as outliers, making the output infeasible for the (α,k,m)-fair clustering problem, so the claimed 12x/24x approximation is unsupported.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: the thresholding rule in OutRound can mark more than m points as outliers, and the paper provides no theoretical bound. The problem definition (Definition 3) restricts outlier sets to size at most m, so if the algorithm excludes more than m points, its output is not a feasible solution to the (α,k,m)-fair clustering problem. Consequently, the chain FR ≤ 4LP' ≤ 12LP* ≤ 12OPT does not establish that IFXO is a 12/24-approximation to the m-outlier optimum; it only bounds the cost on the points that the algorithm chooses to keep, which is an easier problem when the outlier budget is exceeded. The paper itself acknowledges the missing bound in Section 5 and lists deriving one as future work, and Table 2 shows empirical violations (up to 3m outliers for m=10). I considered other potential issues, such as the clipping of reassigned x-values in OutRound and the transfer of the FairRound guarantee to the inlier subproblem, but these are either implicitly handled by the LP constraints or secondary to the feasibility violation. The outlier-count gap is sufficient to reject the paper's main claim; if a bound such as |Z'| ≤ c·m for constant c were proven, or the definition relaxed to allow c·m outliers, the result could be repaired, but as written the central theorem is not supported. Thus the reader's verdict of REJECT stands unchanged.","tokens_in":8957,"tokens_out":14162,"duration_ms":133235,"concrete_test":"Reproduce the IFXO pipeline exactly as in Section 6 on the Bank dataset with m = 10 and k = 5, solving (LP) with CPLEX and thresholding z* at τ = 0. Count the number of points with z*_v > 0. If this count exceeds m (the paper's Table 2 reports up to 30), then the algorithm returns an outlier set violating Definition 3, confirming that the output is infeasible and the approximation claim fails. To check the worst case, also run the same count on a synthetic instance with n = 2m identical points, where an optimal LP solution may set z*_v = m/n for all v.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1 and the following paragraph) requires IFXO to return a feasible (α,k,m)-fair clustering, which by Definition 3 means the outlier set Z' satisfies |Z'| ≤ m. However, Algorithm 2 (OutRound, line 7) sets z'_v = 1 iff z*_v > τ with τ = 0, and the LP constraint (LP2) only bounds the sum of z*_v by m, not the number of positive entries. An optimal LP solution can spread the outlier budget fractionally (e.g., z*_v = m/n for every v), causing the threshold to mark all n points as outliers. The paper concedes this gap explicitly: 'we do not show any bounds for the number of outliers detected' (Section 5), and its own experiments (Table 2) report up to 3m detected outliers for m=10. When |Z'| > m, the output is not a feasible solution to the problem being approximated, and comparing its inlier cost to OPT (an optimal solution with at most m outliers) is invalid because the algorithm is effectively allowed a larger outlier budget. The proof of Theorem 1 bounds only the inlier cost (LPα=2 ≤ 3LPα=1) and does not address feasibility. Without a bound on |Z'|, or an explicit relaxation of the problem definition, the claimed 12x/24x approximation with respect to the m-outlier optimum is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies individually fair k-clustering (k-means and k-median) in the presence of up to m outliers. It introduces a linear program with fractional center, assignment, and outlier variables, solves it, rounds the outlier variables by thresholding at τ=0 (Algorithm 2, OutRound), removes the detected outliers, and applies the FairRound algorithm of [23] to the remaining points. The main theoretical claim is that this yields a 12-approximation for k-means and a 24-approximation for k-median with respect to the optimal cost for the m-outlier problem, and a 16-approximation to the fair radius for inliers. Experiments on three UCI datasets report clustering costs and fairness radius values. The paper explicitly states that no bound is shown on the number of detected outliers (Section 5).","tokens_in":9156,"tokens_out":15407,"duration_ms":136920,"significance":"If the central claims were correct, this would be the first LP-based constant-factor bicriteria approximation for individually fair k-clustering with outliers, extending the prior work of Negahbani and Chakrabarty. The idea of using an LP to identify outliers and then applying a known rounding algorithm is natural, and the paper is transparent about its main limitation. However, because the rounding step can mark more than m points as outliers, the output is not a feasible solution to the (α,k,m)-fair clustering problem of Definition 3, and the claimed cost and fairness guarantees relative to an optimum that excludes at most m outliers are not established. This is a load-bearing gap; the paper should be substantially revised before its main theorem can be accepted.","major_comments":[{"comment":"The rounding rule z'_v = 1 iff z*_v > 0 (Algorithm 2, line 7, with τ=0) can mark more than m points as outliers, because constraint (LP2) only bounds the sum of the fractional outlier values, not the number of positive entries. An LP solution with z*_v = m/n for every v would make all n points labeled outliers. The output is then not a feasible (α,k,m)-fair clustering as defined in Definition 3, and the claimed 12x/24x cost approximation and 16x fair-radius guarantee with respect to an optimum that excludes at most m outliers are not established. The paper explicitly concedes this in Section 5 ('we do not show any bounds for the number of outliers detected') and in the future-work paragraph, and Table 2 reports up to 3m detected outliers for m=10. To repair this, the algorithm should select at most m outliers (e.g., the m largest z* values), which would preserve the inequalities in the proof of Theorem 1; the theorem and experiments must then be restated for the modified procedure.","section":"§5, Theorem 1 and Algorithm 2"},{"comment":"The reassignment loop 'for ∀v ∈ X such that x_vu_OT≠0 do x'_vu' ← x'_vu' + x_vu_OT' runs over all v, including points that were marked as outliers in lines 7-8 and whose x' entries were zeroed in line 8. This gives outlier points nonzero assignment values, contradicting their exclusion and making the subsequent call to FairRound on X_in inconsistent with x'. The proof of Theorem 1 sums only over v∈X\\X_OT, so the pseudocode needs to be changed to restrict the loop to v not in outlier_indices.","section":"Algorithm 2, line 15"},{"comment":"The statement 'LPα=2(x′, y′, z′) ≤ 3LPα=1(x∗, y∗, z∗)' is imprecise: the LP cost does not depend on z, and the proof actually bounds the cost on the inlier set X\\X_OT. More importantly, the chain in Eq. (11)-(12) concludes FR(x',y') ≤ 12 OPT2 without establishing that the algorithm's outlier set has size at most m, so the comparison to OPT2, the optimal cost for the m-outlier problem, is not meaningful. The paper should state the result as an explicit bicriteria approximation (allowing βm outliers) or prove a bound on the number of detected outliers.","section":"§5, Theorem 1 statement and Eq. (11)-(12)"}],"minor_comments":[{"comment":"The expression '1[z*[v] > τ]]' has an extra closing bracket; it should read '1[z*[v] > τ]'.","section":"Algorithm 2, line 7"},{"comment":"The phrase 'Z is denotes as outliers' is ungrammatical; it should be 'Z is the set of outliers' or 'Z denotes the outliers'.","section":"Definition 3"},{"comment":"Table 2 shows that IFXO can detect up to 3m outliers when m=10, but the cost comparisons in Tables 3 and 4 are computed after removing those detected points. Since the baseline iForest removes exactly 10 outliers, the comparisons are not on equal footing and should be discussed or adjusted.","section":"Table 2 and Tables 3-4"},{"comment":"The notation OPT2 and OPT1 is introduced only after Eq. (12); these should be defined before their first use in the text.","section":"§5, notation"},{"comment":"The sentence 'This ensures that the xvu values always decrease whenever a point v is marked as an outlier' is unclear; for τ=0 the x values of marked outliers are set to zero, but the statement should be phrased more precisely.","section":"§5, sentence after Theorem 1 proof sketch"}],"recommendation":"major_revision","confidential_remarks":"The paper acknowledges the main gap (unbounded number of detected outliers) and the proposed fix of selecting the top m z* values is natural; the proof of Theorem 1 would likely go through with that modification, so the result is salvageable. However, as written the main theorem is not valid for the stated problem, and the experiments would need to be redone with a feasible outlier set. The novelty is moderate, since the LP is a direct extension of [23] with an outlier indicator variable, but the paper does identify a new problem variant. I recommend major revision rather than rejection because the central idea is defensible with a local algorithmic change."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first LP for individually fair k-means/k-median with outliers, and the cost-transfer argument (LP' ≤ 3LP*) is clean for the inliers. But the paper's headline guarantee doesn't hold as stated, because OutRound with τ=0 can mark more than m points as outliers, and the problem definition (Def 3) caps the outlier set at m. The authors acknowledge this in Section 5 and their own Table 2 shows up to 3m detections. When that happens, the output is infeasible, and comparing its inlier cost to an optimal solution with m outliers is not valid.\n\nWhat's new and good: the LP with z_v variables, the OutRound reassignment for centers that are also outliers, and the use of the prior FairRound result are all sensible. The proof of Lemma 1 is a straightforward triangle inequality and the 3-factor bound for the LP cost holds for the inlier portion. The paper is also honest: it states plainly that no outlier-count bound is shown.\n\nSoft spots, in order of importance. First, the missing |Z'| bound is load-bearing, not a technicality. An optimal LP solution can spread z* fractionally over many points (e.g., z*_v = m/n for all v), so thresholding at zero marks everything as an outlier. The paper tries to patch this empirically, but an example like that kills the guarantee. Second, Theorem 1's statement is ambiguous: LPα=2(x',y',z') includes the outlier assignments, yet the proof only bounds the inlier cost (X\\X_OUT). If the outlier set is too large, the RHS comparison to OPT doesn't follow. Third, the evaluation is light: single runs, no error bars, and Figure 2 contains a local file path artifact. Those are minor relative to the main gap.\n\nBottom line: it's a promising start on an open problem, and the LP formulation may be repairable—either by proving a bound on the number of positive z*_v's under some separation condition, or by explicitly relaxing the problem to allow up to c*m outliers. As it stands, the central claim is not supported. I'd still send it to a serious referee if the venue tolerates substantive revision, because the idea and the clean inlier cost bound deserve scrutiny and the gap is clearly identified by the authors themselves.\n\nRecommendation: engage with it if you work on fair clustering; otherwise wait for a revision that fixes the feasibility issue.","headline":"The LP is a genuine first step, but the missing bound on detected outliers breaks the claimed approximation.","tokens_in":9761,"tokens_out":2173,"would_cite":false,"duration_ms":19306,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A linear program that marks outlier candidates and then rounds centers gives constant-factor approximation guarantees for individually fair k-means and k-median clustering with outliers.","keywords":["individually fair clustering","outliers","k-means","k-median","linear programming","approximation algorithm"],"falsifier":"On a synthetic instance with a uniquely optimal m-outlier clustering, run the LP and OutRound with threshold 0 and count points with z_v > 0; if any instance yields more than m, the output violates the feasibility constraint of Definition 3 and the claimed 12/24 cost approximation against the m-outlier optimum is not established.","tokens_in":8676,"feed_emoji":"⚖️","tokens_out":14162,"duration_ms":103915,"temperature":0.7,"pith_summary":"The paper claims that individually fair k-clustering can be solved in the presence of outliers by folding outlier detection into a linear program. The algorithm solves the LP, rounds the outlier variables to remove marked points, and then applies a known fair-rounding routine to the remaining points. If correct, the result is that every inlier has a center within 16 times its fair radius, and the clustering cost is within a factor of 12 for k-means or 24 for k-median of the optimal cost that may discard up to m outliers. This is the first work to bring individual fairness to k-means clustering with outliers. The authors also report experiments on three standard datasets, where the number of points marked as outliers stayed at most three times the injected outlier budget.","feed_headline":"12x k-means, 24x k-median: one LP for fair clustering with outliers","feed_subtitle":"Solves one linear program, discards the marked outliers, and bounds fairness and cost for the rest.","key_machinery":"The argument rests on a linear program that couples three families of variables: assignment variables $x_{vu}$, center-opening variables $y_u$, and outlier-indicator variables $z_v$. Constraints limit centers to $k$, outliers to $m$, require every non-outlier to be fully assigned within its fair radius ($LP6$ with $\\alpha = 1$), and forbid an outlier from serving as a center. The OutRound algorithm then rounds $z$ by a zero threshold, and for each outlier that was a center, transfers its assignment mass to the nearest non-outlier point. The load-bearing inequality is Lemma 1: the triangle inequality gives $d(v,u') \\leq 2d(v,u_{OT}) \\leq 2r(v)$ for every point $v$ formerly assigned to an outlier-center, and summing these reassignment costs with the original costs yields $LP_{\\alpha=2}(x',y') \\leq 3\\,LP_{\\alpha=1}(x^*,y^*,z^*)$. This factor-3 cost bound is what converts FairRound's approximation guarantees into the 12/24 cost and 16 radius claims.","core_discovery":"The paper's central discovery is that outlier identification can be folded into the individual-fairness LP itself. The LP uses a variable $z_v$ for each point, with $z_v = 1$ interpreted as 'v is an outlier'; constraints limit the number of marked points to $m$ and forbid a marked point from being a center. After solving the LP, the algorithm OutRound thresholds $z$ at $\\tau = 0$, removes every point with $z_v > 0$, and for any removed point that was acting as a center reassigns its assigned mass to the nearest remaining point. The key bound, Theorem 1, shows that this reassignment increases the LP cost by at most a factor of 3 while degrading the fair-radius constraint from $\\alpha = 1$ to $\\alpha = 2$. Combined with the FairRound algorithm of [23], which gives a 4-approximation for k-means and an 8-approximation for k-median, this yields a 12-approximation to the optimal k-means cost and a 24-approximation to the optimal k-median cost, and a 16-approximation to the fair radius for inliers.","pith_inferences":["The proof of Theorem 1 does not use the constraint that at most m points be marked as outliers, so the factor-3 cost bound holds for whatever set OutRound outputs; the unresolved question is whether the number of marked points can be bounded by a function of m, since otherwise the output may violate the feasibility condition of Definition 3.","The experiments suggest that a positive threshold $\\tau$ could trade a slightly larger cost or fairness slack for fewer detected outliers, and a provable trade-off between $\\tau$ and the number of marked points is a natural next step that the paper leaves open.","OutRound moves all assignment mass from an outlier-center to the single nearest remaining point; splitting that mass among several nearby centers would likely reduce the cost blow-up below the proven factor of 3, though the triangle-inequality argument would need to be reworked.","The computational bottleneck is the large LP, and the experiments restrict attention to 1000-point samples; a coreset or dimension-reduction approach tailored to this LP with outlier variables could let the method scale to full datasets."],"forward_implications":["If the central claim is correct, any dataset with up to m outliers can be clustered so that every inlier has a center within 16 times its fair radius, with cost at most 12 (k-means) or 24 (k-median) times the optimal that is allowed to discard m points.","The outlier-marking LP reduces to the existing no-outlier fair-clustering LP when m = 0, so the algorithm is a strict generalization of previous individually fair clustering.","The factor-3 cost bound is independent of the distance exponent p, so the same outlier-detection and rounding scheme gives constant-factor guarantees for both k-median (p=1) and k-means (p=2).","Because the method only requires solving one linear program and then rounding, it provides a concrete polynomial-time recipe for fair clustering with outliers that works with standard LP solvers."],"supporting_citations":[{"why":"Supplies the FairRound algorithm and its 4-approximation for k-means and 8-approximation for k-median costs, which the final guarantees build on.","marker":"[23]"},{"why":"Defines the fair radius r(v) and the individual fairness constraint that the paper enforces for inliers.","marker":"[18]"},{"why":"Introduces the k-clustering-with-outliers problem and the convention of excluding up to m points from cost and fairness, which the LP's budget constraint mirrors.","marker":"[5]"}],"fun_headline_variants":["One LP finds outliers for individually fair k-clustering","LP rounds outliers away: 12x k-means, 24x k-median","Outlier-aware fair clustering: one LP, then rounding","One LP removes outliers; fair k-clustering 12x shown"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the thresholded outlier set never exceeds the budget m, a fact the paper does not prove and its experiments show can fail by a factor of three.","fun_headline_variants_meta":{"raw":{"variants":["One LP finds outliers for individually fair k-clustering","LP rounds outliers away: 12x k-means, 24x k-median","Outlier-aware fair clustering: one LP, then rounding","One LP removes outliers; fair k-clustering 12x shown"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000571,"raw_usage":{"total_tokens":2719,"prompt_tokens":985,"completion_tokens":1734,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":1668}},"tokens_in":601,"tokens_out":1734,"duration_ms":11166,"temperature":1.0,"reasoning_tokens":1668,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:30:19.146626+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a synthetic instance with a uniquely optimal m-outlier clustering, run the LP and OutRound with threshold 0 and count points with z_v > 0; if any instance yields more than m, the output violates the feasibility constraint of Definition 3 and the claimed 12/24 cost approximation against the m-outlier optimum is not established.","supporting_citations":[{"cited_title":"In: Advances in Neural Information Processing Systems (2021)","cited_arxiv_id":null,"evidence_quote":"Supplies the FairRound algorithm and its 4-approximation for k-means and 8-approximation for k-median costs, which the final guarantees build on."},{"cited_title":"In: ACM-SIAM Symposium on Dis- crete Algorithms (2001)","cited_arxiv_id":null,"evidence_quote":"Introduces the k-clustering-with-outliers problem and the convention of excluding up to m points from cost and fairness, which the LP's budget constraint mirrors."}],"review_version":1}