Friedrich Eisenbrand and Günter Rote:
Fast 2-variable integer programming
In: IPCO 2001 - Proceedings of the 8th Conference on Integer Programming
and Combinatorial Optimization, Utrecht, June 13–15, 2001. Editors: K.
Aardal, B. Gerards. Lecture Notes in Computer Science 2081, Springer-Verlag,
2001, pp. 78–89. doi:10.1007/3-540-45535-3_7
Abstract
We show that a 2-variable integer program defined by m constraints involving
coefficients with at most s bits can be solved with O(m+slogm)
arithmetic operations or with O(m+logmlogs)M(s)
bit operations, where M(s) is the time needed for s-bit
integer multiplication.
Thus, when the number of constraints is fixed, integer programming
in two variables is not harder than greatest common divisor computation.
Our algorithm avoids the binary search that is associated with the usual
approach by letting the objective function slide into the polyhedron, until
the lattice width of the truncated polyhedron equals the flatness constant
from Khintchin's Flatness theorem.
Last update: March 20, 2002.