Parameterized algorithms for block-structured integer programs with large entries

We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs with constraints of the form A_i x + D_i y_i = b_i for all i = 1, ..., n, where A_i and D_i are bounded-size matrices. Intuitively, after choosing a small set of global variables x, the problem decomposes into many bounded-size subproblems. n-fold programs are integer programs with constraints of the form (∑_i C_i y_i = a) and (D_i y_i = b_i for all i = 1, ..., n), again with bounded-size matrices C_i and D_i. This captures knapsack-like settings where variables are partitioned into small groups that obey local constraints, while a few global constraints link all variables. Recent work shows that optimization for both two-stage stochastic programs and n-fold programs is fixed-parameter tractable (FPT) when parameterized by the dimensions of the relevant matrices A_i, C_i, D_i and by the maximum absolute entry in the constraint matrix. A key tool is the Graver basis, which assumes all constraint entries are bounded. We prove that these FPT results persist even when large entries are allowed in the global part of the program: Two-stage stochastic programs (feasibility): FPT when parameterized by the dimensions of A_i and D_i and by the maximum absolute entry of D_i. In particular, A_i may have arbitrarily large entries. Uniform n-fold integer programs (linear optimization): FPT when parameterized by the dimensions of C_i and D_i and by the maximum absolute entry of D_i, provided all C_i are equal to a common matrix C; C may have arbitrarily large entries. The uniformity requirement in the second result is necessary: without it, the problem is NP-hard even for constant parameter values. Both algorithms are weakly polynomial, with running time measured in the total bit size of the input. Methodologically, we move beyond a purely Graver-basis approach. For two-stage stochastic programs, we reduce to an integer program with a bounded number of variables using new insights about the combinatorics of integer cones. For n-fold programs, we reduce the given instance to an exponential-size program with bounded right-hand sides, and then solve it via a reduction to mixed-integer programming with a bounded number of integral variables.