# zbMATH — the first resource for mathematics

Simple and fast algorithms for linear and integer programs with two variables per inequality. (English) Zbl 0831.90089
The authors present an $$O(mn^2\log m)$$ algorithm for solving feasibility in linear programs with up to two variables per inequality (where $$n$$ and $$m$$ are the numbers of variables and inequalities, respectively) which is faster for $$m< n^{O(\log n)}$$ and simpler than all other know algorithm. That algorithm is based on the Fourier-Motzkin elimination method.
Then the authors consider integer programming problems on monotone inequalities (each inequality is of the form $$ax_i- bx_j\leq c$$, where $$a$$ and $$b$$ are positive). They show that both a feasible solution and an optimal solution with respect to an arbitrary objective function can be computed in pseudo-polynomial time.
Finally, they present an application of the Fourier-Motzkin algorithm to identify fat polytopes, the polytopes that contain a sphere which circumscribes an unit hypercube.

##### MSC:
 90C10 Integer programming 05C85 Graph algorithms (graph-theoretic aspects) 90C05 Linear programming 68Q25 Analysis of algorithms and problem complexity 90C27 Combinatorial optimization 90C60 Abstract computational complexity for mathematical programming problems
Full Text: