Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time

We consider n-fold integer programming problems and their
generalizations. These are integer linear programming problems for which
the linear constraints exhibit a (recursive) block-structure: The
problem decomposes into independent sub-problems after deleting a small
number of constraints. Our algorithm relies on parametric search to find
a good fractional solution and a proximity bound between this fractional
solution and an optimal integral solution. Together, this allows us to
find an optimal integer solution in near linear time.