A linear algorithm for integer programming in the plane

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.


Published in:
Mathematical Programming, 102, 2, 249 - 259
Year:
2005
Laboratories:




 Record created 2008-05-13, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)