A linear algorithm for integer programming in the plane

• Published in: Mathematical Programming, vol. 102, num. 2, p. 249 - 259
• Publication date: 2005

We show that a 2-variable integer program, defined by m constraints involving coefficients with at most φ bits, can be solved with O(m+φ) arithmetic operations on rational numbers of size O(φ). © Springer-Verlag 2004.

Reference

• DISOPT-ARTICLE-2005-001
• doi:10.1007/s10107-004-0520-0

Record created on 2008-05-13, modified on 2012-03-21