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.

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: DOI