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

Vol. 7 No. 1 (2012)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.