  In this paper we study the computational complexity of solving a class of
block structured integer programs (IPs) - so called multistage stochastic IPs.
A multistage stochastic IP is an IP of the form $\max \{ c^T x \mid \mathcal{A}
x = b, \,l \leq x \leq u,\, x\text{ integral} \}$ where the constraint matrix
$\mathcal{A}$ consists of small block matrices ordered on the diagonal line and
for each stage there are larger blocks with few columns connecting the blocks
in a tree like fashion. Over the last years there was enormous progress in the
area of block structured IPs. For many of the known block IP classes - such as
$n$-fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and
lower bounds are known concerning their computational complexity. One of the
major gaps that remained however was the parameter dependency in the running
time for an algorithm solving multistage stochastic IPs. Previous algorithms
require a tower of $t$ exponentials, where $t$ is the number of stages, while
only a double exponential lower bound was known. In this paper we show that the
tower of $t$ exponentials is actually not necessary. We can show an improved
running time for the algorithm solving multistage stochastic IPs with a running
time of $2^{(d\||A||_\infty)^{\mathcal{O}(d^{3t+1})}} \cdot poly(d,n)$, where
$d$ is the sum of columns in the connecting blocks and $n$ is the number of
blocks on the lowest stage. In contrast to previous works, our algorithm has
only a triple exponential dependency on the parameters and only doubly
exponential for every constant $t$. By this we come very close the known double
exponential bound (based on the exponential time hypothesis) that holds already
for two-stage stochastic IPs, i.e. multistage stochastic IPs with only two
stages.
