@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.

      ",
  }