2019/04/02 by Friedrich Eisenbrand, Eisenbrand, Friedrich, Christoph Hunkenschröder +9 · 10 citations
Computer Science · Mathematics · #15A #52B #52C #68Q #68R #68W #90B #90C #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC) #acm:15A #acm:52B #acm:52C #acm:68Q #acm:68R #acm:68W #acm:90B #acm:90C #cs.CC #cs.DM #cs.DS #math.CO #math.OC #msc:15A #msc:52B #msc:52C #msc:68Q #msc:68R #msc:68W #msc:90B #msc:90C
paper · pdf · doi:10.48550/arxiv.1904.01361
Revision 3: - corrections to specified complexities (infinite bounds, feasibility, etc.)
openalex publication_date 2019/04/02 · arxiv created 2022/07/29 · arxiv updated 2022/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the general integer programming problem where the number of variables n is a variable part of the input. We consider two natural parameters of the constraint matrix A: its numeric measure a and its sparsity measure d. We show that integer programming can be solved in time g(a,d)\textrmpoly(n,L), where g is some computable function of the parameters a and d, and L is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by a and d, and is solvable in polynomial time for every fixed a and d. Our results also extend to nonlinear separable convex objective functions. Moreover, for linear objectives, we derive a strongly-polynomial algorithm, that is, with running time g(a,d)\textrmpoly(n), independent of the rest of the input data. We obtain these results by developing an algorithmic framework based on the idea of iterative augmentation: starting from an initial feasible solution, we show how to quickly find augmenting steps which rapidly converge to an optimum. A central notion in this framework is the Graver basis of the matrix A, which constitutes a set of fundamental augmenting steps. The iterative augmentation idea is then enhanced via the use of other techniques such as new and improved bounds on the Graver basis, rapid solution of integer programs with bounded variables, proximity theorems and a new proximity-scaling algorithm, the notion of a reduced objective function, and others. As a consequence of our work, we advance the state of the art of solving block-structured integer programs. In particular, we develop near-linear time algorithms for n-fold, tree-fold, and 2-stage stochastic integer programs. We also discuss some of the many applications of these classes.