  We consider integer and linear programming problems for which the linear
constraints exhibit a (recursive) block-structure: The problem decomposes into
independent and efficiently solvable sub-problems if a small number of
constraints is deleted. A prominent example are $n$-fold integer programming
problems and their generalizations which have received considerable attention
in the recent literature. The previously known algorithms for these problems
are based on the augmentation framework, a tailored integer programming variant
of local search. In this paper we propose a different approach. Our algorithm
relies on parametric search and a new proximity bound. We show that
block-structured linear programming can be solved efficiently via an adaptation
of a parametric search framework by Norton, Plotkin, and Tardos in combination
with Megiddo's multidimensional search technique. This also forms a subroutine
of our algorithm for the integer programming case by solving a strong
relaxation of it. Then we show that, for any given optimal vertex solution of
this relaxation, there is an optimal integer solution within $\ell_1$-distance
independent of the dimension of the problem. This in turn allows us to find an
optimal integer solution efficiently. We apply our techniques to integer and
linear programming with $n$-fold structure or bounded dual treedepth, two
benchmark problems in this field. We obtain the first algorithms for these
cases that are both near-linear in the dimension of the problem and strongly
polynomial. Moreover, unlike the augmentation algorithms, our approach is
highly parallelizable.
