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

Katta G. Murty


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.

Full Text:


Algorithmic Operations Research. ISSN: 1718-3235