An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations (Q920841): Difference between revisions

The author gives an algorithm for solving a linear programming problem \(\max \{c^ Tx\); Ax\(\geq b\}\) where A is an \(m\times n\) matrix. The algorithm employs the idea due to \textit{J. Renegar} [Math. Program., Ser. A 40, No.1, 59-93 (1988; Zbl 0654.90050)] and proceeds by constructing a sequence of smaller and smaller polytopes which shrink towards the optimal vertex. At each iteration the algorithm moves from the center of the current polytope to the center of the next one by minimizing a linear function over an ellipsoid. The total number of arithmetic operations required is \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\), where L is bounded by the number of bits in the input; thus the algorithm is faster than that of \textit{N. Karmarkar} [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] by a factor of \(\sqrt{m}\).