SIMPLE AND FAST ALGORITHMS FOR LINEAR AND INTEGER PROGRAMS WITH 2 VARIABLES PER INEQUALITY

The authors present an O(mn(2)log m) algorithm for solving feasibility in linear programs with up to two variables per inequality which is d erived directly from the Fourier-Motzkin elimination method. (The numb er of variables and inequalities are denoted by n and m, respectively. ) The running time of the algorithm dominates that of the best known a lgorithm for the problem, and is far simpler. Integer programming on m onotone inequalities, i.e., inequalities where the coefficients are of opposite sign, is then considered. This problem includes as a special case the simultaneous approximation of a rational vector with specifi ed accuracy, which is known to be NP-complete. However, it is shown th at both a feasible solution and an optimal solution with respect to an arbitrary objective function can be computed in pseudo-polynomial tim e.