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

Authors

  • Katta G. Murty

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.

Downloads

Published

2012-07-26

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

Issue

Section

Articles