×

Towards a genuinely polynomial algorithm for linear programming. (English) Zbl 0532.90061

Summary: A linear programming algorithm is called genuinely polynomial if it requires no more than p(m,n) arithmetic operations to solve problems of order \(m\times n\), where p is a polynomial. It is not known whether such an algorithm exists. We present a genuinely polynomial algorithm for the simpler problem of solving linear inequalities with at most two variables per inequality. The number of operations required is \(O(mn^ 3\) log m). The technique used was developed in a previous paper [Math. Oper. Res. 4, 414-424 (1979; Zbl 0425.90076)] where a novel binary search idea was introduced.

MSC:

90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0425.90076
PDFBibTeX XMLCite
Full Text: DOI