{"id":"e1e7ac7f-102f-4568-b82a-cdce086bdf54","arxiv_id":"2507.03766","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Steinitz-lemma-based algorithm solves combinatorial n-fold ILPs with unbounded non-negative variables, giving 2^{O(k^2)}-time algorithms for Lobbying and Binary Closest String.","lead":"The paper gives a faster algorithm for a class of integer programs called combinatorial n-fold ILPs, using a geometric reordering lemma. It improves the best known running times for Lobbying and Binary Closest String, and matches a theoretical lower bound.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"False slack bound in §4.1: the P2-to-P1 reduction can map a feasible inequality-constrained ILP to an infeasible equality-form P1, so Corollary 7 and the Lobbying/Closest String running times are not established.","rationale":"The central equality-form algorithm (Theorem 1) appears internally coherent: the balancing lemma, the Steinitz-based partial-sum construction, and the shortest-path argument are plausible, and I see no counterexample to the P1 algorithm itself. The load-bearing defect is the inequality-to-equality reduction in Section 4.1. The paper claims a universal slack bound that is false, and a minimal counterexample shows that a feasible P2 can map to an infeasible P1 under the stated construction. Because Corollary 7 is the tool used to obtain the Lobbying and Binary Closest String running times, those results are not proven by the current argument. The applications may be salvageable with problem-specific slack bounds, but that requires rewriting Section 4.1. This matches the reader's weakest-assumption analysis, so no change to the CONDITIONAL verdict is needed.","tokens_in":17669,"tokens_out":29627,"duration_ms":344190,"concrete_test":"Implement the §4.1 construction verbatim on the instance P2: min x subject to x ≤ 10, x ≤ 1, x ∈ Z_{\\ge0}. Check whether the resulting P1 has any feasible integer solution of cost strictly less than ψ/2 = (2+2·1·1)/2 = 2. The only candidates have cost 0 or 1, but the global equality forces s2 = 10−x ≥ 9, while the new local constraint forces s2 ≤ 2; hence no such solution exists. This refutes the claimed reduction. Optionally, repeat for the Lobbying ILP with m=2 and 25 voters of each of the four types, verifying whether total global slack exceeds 2m·max_i c(r_i).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.1's reduction sets b(n+1)=2rΔ·max_i b(i) and asserts that the global slack x(n+1)_{t+1+k}=b(0)[k]−A[k,:]y is at most 2Δ·b(k). This assertion is false: the slack is not bounded by the local right-hand sides. A one-variable counterexample suffices. Take P2: min x subject to x ≤ M, x ≤ L, x ∈ Z_{\\ge0}, with M large and L small. For the feasible solution x=0, the slack in x ≤ M is exactly M. In the §4.1 construction with r=1, Δ=1, the new block has b(n+1)=2L and the global equality becomes x + s1 + s2 = M, where s1 is the expensive slack (cost ψ) and s2 lives in the new block with s2 ≤ 2L. If M > 3L, no solution of cost below ψ/2 exists in the constructed P1 even though x=0 is feasible in P2. Thus the claimed equivalence is false in general. The same failure appears in the Lobbying formulation, where b(0)[k]=−g_k is negative while slack Σ_i b_i B_j(r_i)−g_j is nonnegative and can exceed 2Δ·b(0)[k]. Since Corollary 7 and Theorems 8–9 derive their running times from this reduction, those secondary claims are not established as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a class of combinatorial n-fold integer linear programs in which the diagonal blocks are all-ones row vectors and the top blocks may differ across blocks. The main algorithm first balances a one-row matrix of block indices (Lemma 4), then uses the Steinitz lemma to bound the partial sums of an associated column ordering (Lemma 5), and finally reduces the problem to a shortest-path computation in a layered graph. Theorem 1 claims a running time of O(nt·(nΔ(n+1+4r))^r·q), where q is the sum of the local right-hand sides. Section 4 extends the algorithm to programs with inequality constraints (P2) and derives applications to Lobbying, δ-Multi Strings / Closest String, and Equitable Coloring.","tokens_in":17963,"tokens_out":19633,"duration_ms":220347,"significance":"If correct, the paper would give a conceptually simple, LP-free, non-augmenting algorithm for a natural class of n-fold ILPs, and it would improve the parameter dependence for Lobbying and Binary Closest String to 2^{O(m^2)} and 2^{O(k^2)}, respectively. The proof structure is transparent, the partial-sum bounds are explicit, and the shortest-path formulation is elegant. However, the reduction in Section 4.1 contains false claims, so Corollary 7 and the application theorems are not established as written. The core Theorem 1 is plausible, but the proof of Lemma 4 needs repair before the main result can be considered fully sound.","major_comments":[{"comment":"The text states: 'Observe that ψ/2 is strictly larger than the maximum value the objective function in (P2) can take.' This is false. Since each local constraint is a ≤ constraint, every feasible solution satisfies Σ_j x(i)_j ≤ b(i) for each i, so c^T x can be as large as ∥c∥∞·Σ_i b(i), which may be n times larger than ψ/2 = 1 + ∥c∥∞·max_i b(i). Consequently, the 'other direction' of the reduction, which discards P1 solutions of cost at least ψ/2 as evidence that P2 is infeasible, is invalid.","section":"Section 4.1, definition of ψ"},{"comment":"The reduction sets b(n+1) = 2rΔ·max_i b(i) and asserts that the global slack x(n+1)_{t+1+k} = b(0)[k] − A[k,:]y is 'at most 2Δ·b(k)'. This claim is false in general. For example, consider P2 given by min x subject to x ≤ M, x ≤ L, x ∈ Z_{\\ge 0}, with M > 2L and r = 1, Δ = 1. At the feasible solution x = 0, the slack in x ≤ M equals M, which exceeds b(n+1) = 2L; the constructed P1 then has no solution of cost below ψ/2 even though P2 is feasible. The same phenomenon occurs in the Lobbying formulation, where b(0)[k] = −g_k is negative while the slack can be nonnegative and large. Thus the reduction from P2 to P1 is not an equivalence, and Corollary 7 together with Theorems 8–11 are not established as stated.","section":"Section 4.1, slack bound and construction of b(n+1)"},{"comment":"The proof of Lemma 4 contains an unjustified assertion in its final paragraph: 'By Algorithm 1, we have that imb_{Mσ}(e,q) ≥ 0 for each e ∈ [n]\\{e′}'. This is false when some symbol has zero occurrences, because such a symbol has imbalance identically 0 and can be selected by an arbitrary tie-breaking in the arg min, producing a sequence that is not a permutation of M. The earlier upper-bound argument also asserts that the greedy choice implies all imbalances are positive, which does not follow from the displayed inequalities. The lemma may be true, but the proof needs to be repaired, for instance by restricting the arg min to symbols with remaining occurrences and giving a correct invariant.","section":"Section 3.1, proof of Lemma 4"}],"minor_comments":[{"comment":"The vertex definition says 'For each j ∈ [n]', but the vertices are indexed by positions in the sequence, so this should read 'For each j ∈ [q]'.","section":"Section 3.3, Construction 1"},{"comment":"The quantity ∥c∥∞ should be the maximum absolute value of the objective coefficients; as written, negative objective coefficients would make the bound on ψ/2 meaningless.","section":"Section 4.1, notation for ψ"},{"comment":"The proof divides by b(i) in the expressions occ(i,j)/b(i); if b(i) = 0, these terms are undefined, and the proof should state that blocks with b(i) = 0 are omitted.","section":"Section 3.2, proof of Lemma 5"},{"comment":"The second size constraint says 'if j ∈ {a,...,h}', but the two cases should partition the color classes; the second range is likely {a+1,...,h}.","section":"Section 5.1, Equitable Coloring formulation"}],"recommendation":"major_revision","confidential_remarks":"The Section 4.1 errors are substantial and affect all claimed applications, but they are located in the extensions rather than in the core algorithm of Theorem 1. I would be willing to see a revised version that either repairs the reduction with a correct slack bound and a correct choice of ψ, or states the applications under appropriate additional hypotheses. The overlap with Rohwedder's contemporaneous work is acknowledged transparently, but the authors should ensure that any claims of improvement are supported by the corrected statements."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Brief take: the core P1 algorithm is real and clean, but it is not new—the authors say so themselves—and the P2-to-P1 reduction that powers the Lobbying and Closest String results contains a false bound, so those running times are not established as written. The Steinitz-based balancing argument (Lemmas 4 and 5) is a genuinely nice way to avoid augmentation and LP relaxation for the equality case. The graph DP is standard but carefully presented, and the P1 part should be reproducible from the pseudocode. The paper also does the right thing in flagging Rohwedder's ICALP 2025 paper with identical running times and similar techniques. That is honest scholarship; it just means the main theorem is not a novel result. The serious problem sits in Section 4.1. The reduction from P2 to P1 asserts that the slack in a globally uniform constraint, x(n+1)_{t+1+k} = b(0)[k] - A[k,:]y, is at most 2\\Delta b(k). That is false in general: for an inequality x <= M with x = 0, the slack is M, and if T can contain negative entries (as in Lobbying, where the matrix has -B), the slack can exceed any bound derived from the RHS. The stress-test counterexample is valid: with x <= M and x <= L and M large, the construction forces the slack M to be absorbed by a block of size 2L, so a feasible P2 solution maps to an infeasible P1 instance. Since Corollary 7 and the Lobbying/Closest String theorems rely on this reduction, those claims are not established. Additionally, Lemma 4's proof has an unjustified 'By Algorithm 1, we have imb(e,q) >= 0' line, which is probably repairable but needs a fix. The Lobbying application also has an inconsistent definition of q, though that is minor by comparison. Who is this for? People working on block-structured ILP and parameterized algorithms for social choice and string problems. The P1 part is a useful expository note, but as a paper claiming new running times, it currently overreaches because of Section 4.1. If the authors fix the slack bound—perhaps by setting b(n+1) to a sum of positive parts or by a different construction—the applications would be worth taking seriously. As is, I would recommend sending this to peer review, not desk rejection, but with a clear message that the applications section needs substantial rework and the current corollaries should not be accepted until the reduction is repaired.","headline":"The P1 algorithm is sound and clearly written, but it duplicates Rohwedder's ICALP 2025 result, and the P2-to-P1 reduction that drives the applications has a false slack bound, so the paper's secondary claims are not established.","tokens_in":18554,"tokens_out":3403,"would_cite":false,"duration_ms":39105,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","68Q25","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that combinatorial n-fold ILPs with arbitrary top blocks can be solved directly, without LP relaxations or Graver augmentation, in time $O(nt\\,(n\\Delta(n+1+4r))^r q)$, and that the inequality-tolerant version runs in…","keywords":["n-fold integer programming","combinatorial n-fold ILP","Steinitz lemma","parameterized algorithms","Lobbying","Closest String","block-structured ILP","shortest path"],"falsifier":"Take a Lobbying instance with at least one column where the number of missing ones $g_k$ is positive, so the right-hand side $b^{(0)}[k]=-g_k$ is negative. For any feasible solution, the slack $b^{(0)}[k]-A[k,:]y$ is nonnegative, while the bound $2\\Delta\\,b^{(0)}[k]$ is negative; checking whether the Section 4.1 construction still produces a feasible $(P1)$ point would show whether Corollary 7's reduction is sound.","tokens_in":17402,"feed_emoji":"🧮","tokens_out":11638,"duration_ms":120504,"temperature":0.7,"pith_summary":"This paper presents a direct, non-iterative algorithm for combinatorial $n$-fold ILPs, a class of integer programs where each of $n$ bricks shares a single all-ones row block and the top blocks may differ. The algorithm never solves an LP relaxation and never performs Graver-basis augmentation; instead, it reorders the columns inside each brick so that every partial sum stays close to its proportional share, and then finds an optimal solution as a shortest path in a layered directed acyclic graph. The claimed running time for the equality-only form is $O(nt\\,(n\\Delta(n+1+4r))^r\\cdot q)$, where $q$ is the sum of the last $n$ right-hand-side entries. A reduction from a natural inequality-constrained form is also given, with running time $O(qrt\\,((n+1)\\Delta(n+2+4r))^{r+1})$. These bounds yield $2^{O(m^2)}$ and $2^{O(k^2)}$ algorithms for Lobbying and Binary Closest String, improving on earlier $m^{O(m^2)}$ and $k^{O(k^2)}$ dependencies.","feed_headline":"Steinitz lemma yields direct, LP-free solver for n-fold ILPs","feed_subtitle":"It skips LP relaxations and Graver steps, improving Lobbying and Binary Closest String to 2^{O(m^2)} and 2^{O(k^2)}.","key_machinery":"The engine is the Steinitz lemma, which says that vectors summing to a target can be reordered so that every partial sum stays within a dimension-dependent constant of the proportional line; the paper uses a corollary that bounds each coordinate by $2r\\Delta$. The new one-row balancing lemma (Lemma 4) greedily fills a sequence of block indices so that for every block $i$ and every prefix $j$, the imbalance $\\operatorname{occ}(i,j) - (j/q)b^{(i)}$ lies between $-n$ and $+1$. Combining these two bounds confines each coordinate of the running partial-sum vector to an interval of width $O(n\\Delta(n+r))$, which keeps the layered graph small: at most $1+q(n\\Delta(n+1+4r))^r$ vertices. A shortest path in that graph is the optimal solution.","core_discovery":"The central claim is Theorem 1: the integer program $\\min\\{c^\\top x \\mid Ax=b,\\ x\\in\\mathbb{Z}^{nt}_{\\ge 0}\\}$, with diagonal blocks $D=(1,\\dots,1)$ and arbitrary $r\\times t$ top blocks $T^{(1)},\\dots,T^{(n)}$, can be solved in time $O(nt\\,(n\\Delta(n+1+4r))^r\\cdot q)$ where $q=\\sum_{i} b^{(i)}$. The proof is constructive: any optimal solution gives a multiset of columns from the top blocks; Lemma 4 greedily orders the block labels so that each symbol's imbalance stays between $-n$ and $+1$, and Lemma 5 applies the Steinitz lemma inside each block so that every coordinate of every partial sum stays within $O(n\\Delta(n+r))$ of the proportional line. The algorithm then builds a graph whose vertices are the bounded partial-sum vectors, and a shortest path between the zero vector and $b^{(0)}$ corresponds exactly to an optimal solution. The paper further claims that programs with inequalities in the globally uniform and locally uniform constraints reduce to $(P1)$ with no asymptotic loss, giving Corollary 7 and the applications to Lobbying and $\\delta$-Multi Strings.","pith_inferences":["Editorial inference: the greedy balancing lemma is a discrepancy-style statement for sequences, and the same bounded-imbalance idea could be applied to other block-structured ILPs whose diagonal blocks are not all-ones, potentially replacing augmentation loops with a single reordering step.","Editorial inference: the linear dependence on $q$ means the practical advantage over LP-based algorithms depends on whether $q$ stays comparable to $nt$; for high-multiplicity instances with large $q$, the bound is weaker than the near-linear $nt\\,\\mathrm{polylog}$ algorithms it competes with.","Editorial inference: if the Section 4.1 slack bound fails, as it does when a globally uniform constraint is a lower bound with negative right-hand side, the reduction to $(P1)$ may reject feasible solutions; a modified construction or an additional argument would be needed to keep the Lobbying and Binary Closest String running times intact.","Editorial inference: the shortest-path formulation is objective-agnostic, so the same graph would likely handle separable convex objectives by replacing edge weights with convex increments per column, extending the method beyond linear objectives."],"forward_implications":["For the equality form $(P1)$, the algorithm runs in $O(nt\\,(n\\Delta(n+1+4r))^r\\, q)$ time with no LP relaxation and no Graver-augmentation steps.","For the inequality form $(P2)$, the Section 4.1 reduction gives $O(qrt\\,((n+1)\\Delta(n+2+4r))^{r+1})$ time.","Lobbying can be solved in $2^{O(m^2)}\\cdot w^{O(1)}$ time, improving on the earlier $m^{O(m^2)}$ dependency.","$\\delta$-Multi Strings with a character-wise wildcard-compatible distance is solvable in $(\\Delta k)^{O(k)}|\\Sigma|^{O(k^2)}L^{O(1)}$, and Binary Closest String in $2^{O(k^2)}L^{O(1)}$ time, matching the lower bound hypothesized in [30].","The Equitable Coloring parameterized by vertex cover number $k$ is solvable in $2^{O(k^2)}|V(G)|^{O(1)}$ time in the appendix construction."],"supporting_citations":[{"why":"Original Steinitz lemma: zero-sum bounded vectors can be reordered with all partial sums bounded by the dimension.","marker":"[32]"},{"why":"Sharpened value of the Steinitz constant, giving the quantitative bound used in the partial-sum estimate.","marker":"[15]"},{"why":"Corollary for arbitrary target sums, yielding the $2r\\Delta$ coordinate-wise deviation bound that Lemma 5 relies on.","marker":"[12]"},{"why":"Introduced combinatorial $n$-fold ILPs and the pre-$n$-fold framework; supplies the baseline running time the paper improves for its applications.","marker":"[24]"},{"why":"Current near-linear algorithm for block-structured ILPs; the paper's running time is compared against this bound in the applications.","marker":"[6]"},{"why":"Contemporaneous independent algorithm for a closely related problem with identical parameter dependence; the paper discusses the relation.","marker":"[29]"},{"why":"Provides the integer-programming formulation of Lobbying that the paper instantiates in Section 4.2.","marker":"[4]"}],"fun_headline_variants":["Steinitz lemma gives direct, LP-free n-fold ILP solver","Faster n-fold ILP algorithm via Steinitz lemma","Steinitz lemma simplifies n-fold ILP solving","New combinatorial n-fold ILP algorithm beats LP-based methods","Direct n-fold ILP algorithm skips LP relaxations and Graver steps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reduction from inequality-constrained programs $(P2)$ to the equality form $(P1)$ assumes that the slack in each globally uniform constraint is at most $2\\Delta$ times that constraint's right-hand side; when a globally uniform constraint is a lower bound, the right-hand side can be negative while the slack is nonnegative, so the assumption is not automatically satisfied.","fun_headline_variants_meta":{"raw":{"variants":["Steinitz lemma gives direct, LP-free n-fold ILP solver","Faster n-fold ILP algorithm via Steinitz lemma","Steinitz lemma simplifies n-fold ILP solving","New combinatorial n-fold ILP algorithm beats LP-based methods","Direct n-fold ILP algorithm skips LP relaxations and Graver steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000819,"raw_usage":{"total_tokens":3620,"prompt_tokens":1013,"completion_tokens":2607,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":629,"completion_tokens_details":{"reasoning_tokens":2519}},"tokens_in":629,"tokens_out":2607,"duration_ms":21954,"temperature":1.0,"reasoning_tokens":2519,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:06:19.078366+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a Lobbying instance with at least one column where the number of missing ones $g_k$ is positive, so the right-hand side $b^{(0)}[k]=-g_k$ is negative. For any feasible solution, the slack $b^{(0)}[k]-A[k,:]y$ is nonnegative, while the bound $2\\Delta\\,b^{(0)}[k]$ is negative; checking whether the Section 4.1 construction still produces a feasible $(P1)$ point would show whether Corollary 7's reduction is sound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Sharpened value of the Steinitz constant, giving the quantitative bound used in the partial-sum estimate."},{"cited_title":"Combinatorial n-fold integer programming and applications","cited_arxiv_id":null,"evidence_quote":"Introduced combinatorial $n$-fold ILPs and the pre-$n$-fold framework; supplies the baseline running time the paper improves for its applications."},{"cited_title":"Block-structured integer and linear programming in strongly polynomial and near linear time","cited_arxiv_id":null,"evidence_quote":"Current near-linear algorithm for block-structured ILPs; the paper's running time is compared against this bound in the applications."},{"cited_title":"ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines","cited_arxiv_id":"2501.04859","evidence_quote":"Contemporaneous independent algorithm for a closely related problem with identical parameter dependence; the paper discusses the relation."},{"cited_title":"Woeginger","cited_arxiv_id":null,"evidence_quote":"Provides the integer-programming formulation of Lobbying that the paper instantiates in Section 4.2."}],"review_version":1}