Simple and fast algorithms for linear and integer programs with two variables per inequality. (English) Zbl 0831.90089

Hochbaum, Dorit S.; Naor, Joseph

SIAM J. Comput. 23, No. 6, 1179-1192 (1994).

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.

Reviewer: D.Marinescu (Braşov)

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

Keywords:

pseudo-polynomial algorithm; feasibility in linear programs; Fourier- Motzkin elimination; fat polytopes