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.

  PostScript file (gzippedpdf file (gzipped)
other papers about this subject
Last update: March 20, 2002.