Vol 7 No 1 (2012)
Articles

O(m) Bound on Number of Iterations in Sphere Methods for LP

Published July 26, 2012
How to Cite
Murty, K. G. (2012). O(m) Bound on Number of Iterations in Sphere Methods for LP. Algorithmic Operations Research, 7(1), Pages 30 - 40. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/19441

Abstract

Consider the linear program (LP): minimize z = cx, subject to Ax ≥ b, where A is an m × n matrix. Sphere methods (SMs) for solving this LP were introduced in Murty [5, 6], even though this name was not used there. Theorems in those papers claimed that a version of this method needs at most O(m) iterations to solve this LP, however Mirzaian [2] pointed out an error in the proofs of these theorems there. Here we prove the claim using the geometry of inspheres. Also the results in this paper provide a solution to the special case of the open problem 2 in page 441 of the book Murty [7] dealing only with inspheres encountered in the SM.