Block-structured integer programs, and n-fold ILPs in particular, provide a powerful framework for parameterized algorithm design, with applications including high-multiplicity scheduling, fair division, and computational social choice.Existing algorithms in the literature typically rely on one or more of the following techniques: Graver augmentation, where one starts from a feasible solution and iteratively improves it by finding suitable augmentation steps; solving a linear relaxation of the integer program; or decomposition- and proximity-based arguments.In this talk, I will present a direct algorithm for a class of combinatorial n-fold ILPs with non-negative, unbounded variables. The algorithm is based on a structural reordering argument using the Steinitz lemma: an optimal solution can be represented so that its partial sums remain in a bounded region. This boundedness leads to a finite-state shortest-path dynamic program.The resulting algorithm avoids both augmentation and LP relaxations, and its running time is linear in the total number of selected columns, up to a parameter-dependent factor. I will explain the balancing argument, the dynamic program, and how the resulting bound compares with existing algorithms for n-fold integer programming.
