  Many fundamental NP-hard problems can be formulated as integer linear
programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is
exponential only in the dimension of the program, and polynomial in the size of
the ILP. That algorithm became a ubiquitous tool in the design of
fixed-parameter algorithms for NP-hard problems, where one wishes to isolate
the hardness of a problemby some parameter. However, in many cases using
Lenstra's algorithm has two drawbacks: First, the run time of the resulting
algorithms is often doubly-exponential in the parameter, and second, an ILP
formulation in small dimension cannot easily express problems involving many
different costs.
  Inspired by the work of Hemmecke, Onn and Romanchuk [Math. Prog. 2013], we
develop a single-exponential algorithm for so-called combinatorial n-fold
integer programs, which are remarkably similar to prior ILP formulations for
various problems, but unlike them, also allow variable dimension. We then apply
our algorithm to a few representative problems like Closest String, Swap
Bribery, Weighted Set Multicover, and obtain exponential speedups in the
dependence on the respective parameters, the input size, or both.
  Unlike Lenstra's algorithm, which is essentially a bounded search tree
algorithm, our result uses the technique of augmenting steps. At its heart is a
deep result stating that in combinatorial n-fold IPs, existence of an
augmenting step implies existence of a \local" augmenting step, which can be
found using dynamic programming. Our results provide an important insight into
many problems by showing that they exhibit this phenomenon, and highlights the
importance of augmentation techniques.
