@Article{BarRaw99, author = "R. Bar-Yehuda and Dror Rawitz", title = "Efficient Algorithms for Integer Programs with Two Variables per Constraint", journal = "Algorithmica (to apear)", year = "1999", abstract = " Given a bounded integer program with n variables and m constraints, each with two variables, we present an O(mU) time and O(m) space feasibility algorithm for such integer programs, where U is the maximal variable range size. We show that with the same complexity we can find an optimal solution for the positively-weighted minimization problem for {\em monotone} systems. Using the local-ratio technique we develop an O(nmU) time and O(m) space 2-approximation algorithm for the positively-weighted minimization problem for the general case. We further generalize all results to nonlinear constraints (called {\em axis-convex constraints}) and to nonlinear (but monotone) weight functions. Our algorithms are not only better in complexity than other known algorithms, but also considerably simpler, and they contribute to the understanding of these very fundamental problems. ", }