Integer programming in the plane

In this work we study the problem of integer programming in fixed dimension, with a particular focus on the problem in dimension 2. Integer programming in dimension 2 is linked to elementary algorithmic number theory. In particular, the problem of computing the greatest common divisor of 2 integers is a 2-dimensional IP (that clearly can be solved by the Euclidean Algorithm). Many results in IP in dimension 2 have their foundation in the theory of lattices and continued fractions. IP in dimension 2 has been extensively studied and today many algorithms are known to solve an integer problem in dimension 2 in polynomial time. Specifically, in this work we study the currently fastest algorithm which solves an integer problem in dimension 2, due to Eisenbrand, Rote and Laue. The algorithm takes O(m + k) arithmetic operations, where m is the number of constraints and k is the maximum binary encoding length of the coefficients involved. This algorithm is believed to be optimal.