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 of the form Aix + Diyi = bi for all i = 1,…, n, where Ai and Di are bounded-size matrices. Intuitively, this form corresponds to the setting when after setting a small set of global variables x, the program can be decomposed into a possibly large number of bounded-size subprograms. On the other hand, n-fold programs are integer programs of the form and Diyi = bi for all i = 1,…,n, where again Ci and Di are bounded-size matrices. This form is natural for knapsack-like problems, where we have a large number of variables partitioned into small-size groups, each group needs to obey some set of local constraints, and there are only a few global constraints that link together all the variables.