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 \Aᵢ x + Dᵢ yᵢ = bᵢ for all i=1, , n\, where Aᵢ and Dᵢ are bounded-size matrices. On the other hand, n-fold programs are integer programs of the form \{₈=₁ⁿ Cᵢyᵢ=a and Dᵢyᵢ=bᵢ for all i=1, , n\}, where again Cᵢ and Dᵢ are bounded-size matrices. It is known that solving these kind of programs is fixed-parameter tractable when parameterized by the maximum dimension among the relevant matrices Aᵢ, Cᵢ, Dᵢ and the maximum absolute value of any entry appearing in the constraint matrix. We show that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove that: - The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices Aᵢ, Dᵢ and by the maximum absolute value of the entries of matrices Dᵢ. That is, we allow matrices Aᵢ to have arbitrarily large entries. - The linear optimization problem for n-fold integer programs that are uniform -- all matrices Cᵢ are equal -- is fixed-parameter tractable when parameterized by the dimensions of matrices Cᵢ and Dᵢ and by the maximum absolute value of the entries of matrices Dᵢ. That is, we require that Cᵢ=C for all i=1, , n, but we allow C to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is NP-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input. 49 pages. This is the TheoretiCS journal version