Megiddo, Nimrod Towards a genuinely polynomial algorithm for linear programming. (English) Zbl 0532.90061 SIAM J. Comput. 12, 347-353 (1983). 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. Cited in 1 ReviewCited in 27 Documents MSC: 90C05 Linear programming 68Q25 Analysis of algorithms and problem complexity Keywords:convex minimization; computational complexity; genuinely polynomial algorithm; linear inequalities; at most two variables per inequality; binary search Citations:Zbl 0425.90076 PDFBibTeX XMLCite \textit{N. Megiddo}, SIAM J. Comput. 12, 347--353 (1983; Zbl 0532.90061) Full Text: DOI