{"id":"137aee06-06ad-4039-a3a7-416c6d8c5e1c","arxiv_id":"2506.08110","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Breach uses padded decompositions and a flow-based assignment to achieve an approximation ratio of sqrt(log m)/(3m) for fair max-min diversification when k <= m.","lead":"The paper introduces Breach, a randomized algorithm for fair max-min diversification that selects k diverse items while enforcing per-group lower and upper bounds. Its theoretical guarantee improves the best known polynomial-time ratio by a sqrt(log m) factor in the few-representatives regime, and experiments show it is competitive with prior baselines.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2 defines α=√(log m/m), but the stated √(log m)/(3m) guarantee requires α=√(log m)/m; with the printed α, the key probability bound in Proposition 4 fails and the theorem does not follow as written.","rationale":"The reader's weakest-assumption identification is the metric triangle inequality, but that is an explicit assumption of Problem 1 and is used legitimately in Propositions 2, 4, and 5; it is not the most fragile point. The real load-bearing issue is an internal parameter mismatch: Algorithm 2 and Section 3.2 set α=√(log m/m), while the stated approximation ratio and Proposition 7 require α=√(log m)/m. Under the printed α, the probability proof in Proposition 4 contains the false inequality log m ≥ 2ωm; for large m, ωm is super-polynomially larger than log m, and the claimed Ω(1/m) success probability is not established. This is a concrete formal inconsistency rather than a difference with existing consensus or a stylistic concern. If the intended correction α=√(log m)/m is adopted, the proof chain closes and the central claim stands, so the paper is not fatally flawed. The Section 3.5 practical improvements also deviate from the analyzed algorithm, but that is a separate limitation and does not affect the theoretical theorem. Because the reader already gave a CONDITIONAL verdict and our concern adds a specific condition rather than overturning the result, the appropriate recommendation is to keep the verdict unchanged while requiring the parameter correction to be made explicit.","tokens_in":16683,"tokens_out":15506,"duration_ms":195704,"concrete_test":"Recompute Proposition 4 under the printed α=√(log m/m) at m=10^6: log m ≈ 13.8 but 2ωm ≈ 2.86×10^5, so the inequality 'log m ≥ 2ωm' fails by orders of magnitude; also check m=2, where Δ2=0 makes the random radius interval empty. Then recompute with α=√(log m)/m and confirm that the inequality holds for large m and that γα reproduces the stated √(log m)τ/(3m). This settles whether the theorem is proven for the algorithm as written or only for a corrected parameter.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 passes through Proposition 4, whose key step is the bound p(o is a guard) ≤ ω=4α log(4mα), followed by the assertion that log m ≥ 2ωm and hence (1−ω)^m ≥ 1/m. This assertion is false with the α printed in Algorithm 2 and Section 3.2, namely α=√(log m/m): then ωm = 4√(m log m) log(4√(m log m)), which grows like √m (log m)^{3/2}, far faster than log m. At m=10^6, log m ≈ 13.8 while 2ωm ≈ 2.86×10^5; at m=2, Δ2=⌊1/(2α)⌋=0, so the random radius interval is empty. Consequently the claimed Ω(1/m) success probability, and with it the T·m repetition bound and Theorem 1, does not follow for the algorithm as written. Consistency with Proposition 5 (div(S)≥γα) and Proposition 7 (√(log m)τ/(3m)) forces α=√(log m)/m; with that value ωm = 4√(log m) log(4√(log m)) = o(log m), so the proof closes. The manuscript therefore contains a load-bearing parameter mismatch: the algorithm in the text is not the algorithm whose guarantee is proved.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the fair max-min diversification (FMMD) problem in the regime where each color contributes at most a few representatives (k ≤ m). It proposes a randomized algorithm, Breach, built in three phases: a preprocessing step that prunes each color so that same-color points are well separated; a random CKR-style padded decomposition with a set of 'guard' vertices removed; and a maximum-flow assignment that maps clusters to colors while respecting the interval constraints. The main theoretical claim, Theorem 1, is that when k ≤ m, Breach approximates FMMD within a factor of sqrt(log m)/(3m) in polynomial time, improving on the previous polynomial-time 1/(m+1) bound by a factor of Theta(sqrt(log m)). Two variants are given: a slower one with ratio sqrt(log m)/(3m) and a faster one with ratio sqrt(log m)/(5m). The paper also reports experiments on four real-world datasets and synthetic data, comparing Breach with FairFlow, GreedyFlow, and the coreset-based Core algorithm.","tokens_in":16945,"tokens_out":10566,"duration_ms":126481,"significance":"If the main theorem holds, this is a genuine asymptotic improvement over the state of the art for polynomial-time FMMD approximation in the few-representatives regime. The CKR-partition approach is an interesting and non-obvious technique for this problem, and the flow-based assignment is a clean way to handle the general interval constraints rather than the exact-size constraints studied in prior work. The availability of source code and the experimental comparison with existing baselines are also strengths. However, the main guarantee as stated is not established for the algorithm as printed, because the definition of alpha in Algorithm 2 and Section 3.2 does not match the value of alpha used in the proofs. This is a load-bearing inconsistency that a revision must fix. The core idea is sound and the required fix appears local, so the paper merits a major revision rather than rejection.","major_comments":[{"comment":"There is a parameter mismatch in the definition of alpha. Algorithm 2 line 1 and Section 3.2 define alpha = sqrt(log m / m), but the proofs of Propositions 4 and 5 and the ratio in Proposition 7 require alpha = sqrt(log m) / m. With the printed value, the key inequality log m >= 2*omega*m from Proposition 4 fails for all sufficiently large m: since omega = 4*alpha*log(4*m*alpha), we get omega*m = 4*sqrt(m*log m)*log(4*sqrt(m*log m)), so at m = 10^6, log m is about 13.8 while 2*omega*m is about 2.86*10^5. The chain (1-omega)^k >= exp(-omega*m/(1-omega)) >= 1/m, and with it the claimed Omega(1/m) success probability, therefore does not follow. In addition, for m = 2 the printed value gives Delta_2 = floor(1/(2*alpha)) = 0 while Delta_1 = 1, so R is drawn from an empty interval. Replacing alpha by sqrt(log m)/m makes Delta_2 = floor(m/(2*sqrt(log m))) >= 1 and gives omega*m = 4*sqrt(log m)*log(4*sqrt(log m)) = o(log m), which closes the proof. Consequently, the algorithm whose guarantee is proved is not the algorithm stated in the text.","section":"Section 3.2, Algorithm 2, Propositions 4, 5, and 7"},{"comment":"The displayed chain for the probability that O has no guards has the wrong direction. The text states p(O not having guards) = product over o in O of p(o is not a guard) <= (1-omega)^k, but since p(o is a guard) <= omega, each factor is at least 1-omega and the product is at least (1-omega)^k. As printed, the subsequent lower bound (1-omega)^k >= 1/m does not imply the desired lower bound on the success probability. The surrounding argument evidently intends the >= direction, but the displayed inequality must be corrected for the proof to be valid.","section":"Proposition 4, proof"},{"comment":"The running-time bound for the faster variant is missing one factor of m. In that variant the pruned space U has O(km) points, and each call to Decompose costs O(R*|U|^2) = O(m*(km)^2) = O(k^2*m^3), since R is O(1/alpha) = O(m) with the corrected alpha. Algorithm 4 repeats line 3 T*m times, so the total decomposition cost is O(T*m^4*k^2), not O(T*m^3*k^2) as stated in the proof of Proposition 8 and in Table 1. This does not destroy polynomiality, but the stated complexity claim is incorrect and should be corrected (or the repetition count should be defined differently).","section":"Proposition 8 and Table 1"}],"minor_comments":[{"comment":"The call to Assign uses {k_i} as the upper-bound argument, but the notation for upper bounds elsewhere is {u_i}; {k_i} is not defined. This should be corrected to Assign({D_i}, {ell_i}, {u_i}, k).","section":"Algorithm 4, line 5"},{"comment":"The panel label 'Celab (S+A)' contains a typo and should read 'CelebA (S+A)'.","section":"Section 4, Figure 3"},{"comment":"The word 'inapproxabimility' is a typo and should be 'inapproximability'.","section":"Section 5 (Conclusions)"},{"comment":"The phrase 'This comes yields a weaker guarantee' is grammatically incomplete; it should be 'This yields a weaker guarantee'.","section":"Section 3.4"},{"comment":"The sentence 'It is easy to verify that Delta_1 <= Delta_2 for m >= 1' is not true with the printed value of alpha when m = 2, because Delta_2 = 0 and Delta_1 = 1. After the alpha correction, the statement should be stated with the required lower bound on m.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":"The alpha mismatch in Section 3.2 is the main obstacle to the paper's central claim, and it is local and fixable. The running-time bound in Proposition 8 should also be corrected. I recommend major revision rather than rejection, since the underlying decomposition and flow arguments are otherwise coherent and the result would be a meaningful improvement if the parameterization is fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real contribution here is using CKR padded decompositions for max-min fair diversity, and the flow network that handles general interval fairness constraints. The high-level cluster-then-assign structure isn't new—it follows Addanki et al. and Moumoulidou et al.—but the decomposition technique and the generality of the constraints are. The proofs of Props 2, 3, 5, and 6 are clean, and the assignment flow argument in Prop 6 is correct. If the central claim holds, the improvement from 1/(m+1) to sqrt(log m)/(3m) in the few-representatives regime is a real step forward.\n\nThe problem is that the central claim doesn't hold for the algorithm as written. Algorithm 2 sets α = sqrt(log m / m), but the proof of Prop 4 needs α = sqrt(log m) / m. With the printed α, the bound log m ≥ 2ωm fails: ωm grows like sqrt(m log m) log(m), not o(log m). For m=2, Δ2 becomes 0, breaking the interval for R. So the success probability Ω(1/m) and the repeated-trial argument in Prop 7 are not justified. The reader's take treated this as a minor typo in the direction of a product inequality; it's actually a parameter mismatch between the algorithm and the analysis. The good news is that changing α to sqrt(log m)/m fixes it, and the rest of the proof then closes. But Theorem 1 as stated is false for the algorithm in the text.\n\nThe experiments are suggestive but not fully controlled. The paper admits that the headline comparison is partially explained by looser constraints on Breach, and the promised results with identical constraints are not shown. That's a presentation gap, not a fatal flaw.\n\nAll of this is addressable. The idea is sound, the analysis framework is mostly rigorous, and the fix is a one-line change. I'd send this to peer review, with a specific request that the authors correct α, verify the bounds hold for small m, and show the same-constraint experiments. It deserves a serious referee despite the current error.","headline":"Good idea, solid proofs around a load-bearing parameter typo: Algorithm 2 defines α differently from what the proof of Prop 4 requires, so the main theorem as written is false; the fix is simple and the paper deserves review.","tokens_in":17498,"tokens_out":2462,"would_cite":false,"duration_ms":28868,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper's central claim is that when $k \\le m$, a randomized algorithm based on padded decompositions approximates fair max-min diversification within a factor of $\\sqrt{\\log m}/(3m)$, improving the previous best polynomial-time factor…","keywords":["fair diversity maximization","max-min diversification","padded decompositions","randomized algorithms","approximation algorithms","CKR partitions","fairness constraints"],"falsifier":"On a small metric instance (say $n \\le 12$ points, $m \\le 4$ colors, $k \\le m$), compute the optimal FMMD value by exhaustive search, run Breach with the stated parameters for many repetitions, and record the worst ratio of the output's diversity to the optimum; a ratio below $\\sqrt{\\log m}/(3m)$ within the claimed failure regime would refute Theorem 1.","tokens_in":16446,"feed_emoji":"🎲","tokens_out":11398,"duration_ms":106959,"temperature":0.7,"pith_summary":"The paper asks: when a dataset is partitioned into $m$ labeled groups, how can one select $k$ items so that the smallest pairwise distance is as large as possible while each group stays within its lower and upper representation bounds? Its central claim is that in the 'few representatives' regime ($k \\le m$), a randomized algorithm called Breach approximates this fair max-min diversification problem within a factor of $\\sqrt{\\log m}/(3m)$ in polynomial time, improving the previous best polynomial-time guarantee of roughly $1/(m+1)$. The improvement matters because many applications—forming committees, siting facilities, summarizing documents—want only a handful of representatives per category, and a provably larger minimum distance means a more spread-out, more useful selection. The paper proves the guarantee through a three-stage pipeline and confirms on real datasets that it matches or beats existing polynomial-time methods.","feed_headline":"Boosts fair diversity ratio to sqrt(log m)/(3m)","feed_subtitle":"A polynomial-time algorithm improves the old 1/(m+1) approximation for choosing k diverse items with per-label quotas.","key_machinery":"The engine is the CKR random partition (a standard padded decomposition of a metric space into random clusters with bounded diameter), applied with parameter $\\alpha = \\sqrt{\\log m/m}$. The decomposition builds a graph on points with edges between points closer than $\\gamma\\alpha$, orders the points by a random permutation, and carves out clusters as BFS balls of a random radius; vertices on cluster boundaries are discarded as guards. Two facts make the argument work: any cluster ball of radius $\\Delta_2$ has diameter below $\\gamma$ by the triangle inequality, so after pruning it contains at most one point of each color (at most $m$ points total), and a known bound on the probability that a given point becomes a guard yields a per-point survival probability that compounds to $\\Omega(1/m)$ across the $k$ points of an optimal solution. The assignment phase is an integral max-flow network with a node per cluster and per color, plus a slack node $z$ that absorbs the difference between lower and upper bounds, which is what allows general $\\ell_i \\le |S \\cap V_i| \\le u_i$ constraints rather than exact quotas.","core_discovery":"The central result is Theorem 1: if $k \\le m$, Algorithm 4 (Breach) runs in polynomial time and, with high probability, returns a feasible set whose diversity score is at least $\\sqrt{\\log m}/(3m)$ times the optimum for the fair max-min diversification problem with lower and upper bounds $\\ell_i, u_i$ per color. The algorithm first prunes each color so that same-color points are at distance at least a threshold; it then randomly decomposes the pruned space into clusters using a CKR padded partition and removes boundary 'guard' points, so that any two surviving clusters are at distance at least $\\gamma\\alpha$ with $\\alpha = \\sqrt{\\log m/m}$; finally, a max-flow network assigns clusters to colors and extracts one point per chosen cluster, which yields a feasible solution whenever one exists in the decomposition. The proof shows that an optimal solution survives the decomposition with probability $\\Omega(1/m)$, and that any set with at most one point per surviving cluster is automatically diverse.","pith_inferences":["The $\\sqrt{\\log m}$ factor is characteristic of padded-decomposition arguments, so a deterministic alternative would likely need a different technique to remove the log factor; a natural test is whether the decomposition's guard probability can be improved for structured metrics such as Euclidean spaces.","The flow-assignment stage is agnostic to how clusters are produced, so the same decomposition-plus-flow recipe might apply to other constrained diversity objectives, such as fair max-sum diversification, by replacing only the assignment network.","The paper's experiments show a few iterations suffice in practice, suggesting the worst-case $\\Omega(1/m)$ survival probability is pessimistic; a tighter empirical or average-case analysis could reduce the $T m$ repetitions without hurting the guarantee.","For $k$ proportional to $m$ ($k \\le \\beta m$), the paper notes the success probability drops to $\\Omega(1/m^\\beta)$, so the method degrades in repetitions as $\\beta$ grows; closing this gap for linear $k$ would extend the few-representatives regime substantially."],"forward_implications":["Any application that needs at most one or a few representatives per category—committee formation, facility siting, document summarization—can now guarantee a minimum pairwise distance within $\\sqrt{\\log m}/(3m)$ of optimal in polynomial time, where the old guarantee was only about $1/(m+1)$.","Because the flow assignment handles arbitrary lower and upper bounds, the algorithm covers fairness constraints that the earlier exact-quota methods did not, so the theoretical improvement extends to the full FMMD problem as defined in the paper.","The two parameter settings give a user a trade-off: the $O(T m^2 n^2)$ version with ratio $\\sqrt{\\log m}/(3m)$, or the faster $O(k m n + T m^3 k^2)$ version with ratio $\\sqrt{\\log m}/(5m)$, both polynomial and practical on the tested datasets.","The guarantee extends to $k > m$ by adding $k-m$ artificial empty colors, so the polynomial-time algorithm covers the entire FMMD problem, with the ratio degrading smoothly to $\\sqrt{\\log m'}/(3m')$ for $m' = \\max(k,m)$.","The success probability can be amplified to $1 - 2^{-\\Omega(T)}$ by repeating the random decomposition $T m$ times, so the high-probability guarantee is robust."],"supporting_citations":[{"why":"Supplies the CKR random partition used in the decomposition phase; its padded-decomposition properties drive the guard-probability bound.","marker":"[10]"},{"why":"Provides the known lemma bounding the probability that a point is removed as a guard, used in the proof of Proposition 4.","marker":"[23]"},{"why":"The current best polynomial-time approximation ($1/(m+1)$) that the paper improves; also motivates the cluster-and-assign framework.","marker":"[3]"},{"why":"The earlier well-separated-clusters algorithm for fair MMD; Proposition 3 adapts a proof from its Theorem 6.","marker":"[33]"},{"why":"Defines the FMMD problem with lower and upper quotas and provides the datasets and baseline implementations used in the experiments.","marker":"[42]"},{"why":"Gives the almost-linear-time max-flow algorithm that bounds the running time of the assignment phase.","marker":"[38]"}],"fun_headline_variants":["Fair diversity ratio now sqrt(log m)/(3m)","Polynomial-time fair diversity hits sqrt(log m)/(3m)","New approximation for fair diversity: sqrt(log m)/(3m)","Fair diversity with few reps: sqrt(log m)/(3m) bound","Improving fair diversity approximation to sqrt(log m)/(3m)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that distances obey the triangle inequality: the pruning step relies on it to map distinct optimal points to distinct surviving points, and the decomposition relies on it to conclude that a cluster ball contains at most one point of each color.","fun_headline_variants_meta":{"raw":{"variants":["Fair diversity ratio now sqrt(log m)/(3m)","Polynomial-time fair diversity hits sqrt(log m)/(3m)","New approximation for fair diversity: sqrt(log m)/(3m)","Fair diversity with few reps: sqrt(log m)/(3m) bound","Improving fair diversity approximation to sqrt(log m)/(3m)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000253,"raw_usage":{"total_tokens":1586,"prompt_tokens":989,"completion_tokens":597,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":511}},"tokens_in":605,"tokens_out":597,"duration_ms":6551,"temperature":1.0,"reasoning_tokens":511,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:22:13.296710+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small metric instance (say $n \\le 12$ points, $m \\le 4$ colors, $k \\le m$), compute the optimal FMMD value by exhaustive search, run Breach with the stated parameters for many repetitions, and record the worst ratio of the output's diversity to the optimum; a ratio below $\\sqrt{\\log m}/(3m)$ within the claimed failure regime would refute Theorem 1.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the CKR random partition used in the decomposition phase; its padded-decomposition properties drive the guard-probability bound."},{"cited_title":"Two (Known) Results About Graphs with No Short Odd Cycles","cited_arxiv_id":"1810.01832","evidence_quote":"Provides the known lemma bounding the probability that a point is removed as a guard, used in the proof of Proposition 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The current best polynomial-time approximation ($1/(m+1)$) that the paper improves; also motivates the cluster-and-assign framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The earlier well-separated-clusters algorithm for fair MMD; Proposition 3 adapts a proof from its Theorem 6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the FMMD problem with lower and upper quotas and provides the datasets and baseline implementations used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the almost-linear-time max-flow algorithm that bounds the running time of the assignment phase."}],"review_version":1}