On the complexity of integer programming in fixed dimension

Summary form only given. Integer programming is the problem of maximizing a linear function over the integer vectors which satisfy a given set of inequalities. A wide range of combinatorial optimization problems can be modeled as integer programming problems. But integer programming is not only related to combinatorics. The greatest common divisor of two integers a and b is the smallest integer combination xa+yb such that xa+yb ⩾ 1. This is an integer program in two variables. This fact links integer programming also to the algorithmic theory of numbers. In this talk, we review Lenstra 's algorithm for integer programming in fixed dimension, which runs in time O(mφ + φ2), where m is the number of constraints and each constraint has encoding length at most φ. We then show that an integer programming problem in fixed dimension with a fixed number of constraints can be solved in linear time. This matches with the complexity of the Euclidean algorithm. It follows that an integer program in fixed dimension can be solved in an expected running time of O(m + (logm)φ)