### A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimensionA simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

Access Restriction
Subscribed

 Author Adler, Ilan ♦ Megiddo, Nimrod Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1985 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract It has been a challenge for mathematicians to confirm theoretically the extremely good performance of simplex-type algorithms for linear programming. In this paper the average number of steps performed by a simplex algorithm, the so-called self-dual method, is analyzed. The algorithm is not started at the traditional point (1, … , l)T, but points of the form (1, ε, ε2, …)T, with ε sufficiently small, are used. The result is better, in two respects, than those of the previous analyses. First, it is shown that the expected number of steps is bounded between two quadratic functions $\textit{c}1(min(\textit{m},$ $\textit{n}))2$ and $\textit{c}2(min(\textit{m},$ $\textit{n}))2$ of the $\textit{smaller}$ dimension of the problem. This should be compared with the previous two major results in the field. Borgwardt proves an upper bound of $\textit{O}(\textit{n}4\textit{m}1/(\textit{n}-1))$ under a model that implies that the zero vector satisfies all the constraints, and also the algorithm under his consideration solves only problems from that particular subclass. Smale analyzes the self-dual algorithm starting at (1, … , 1)T. He shows that for any fixed $\textit{m}$ there is a constant $\textit{c}(\textit{m})$ such the expected number of steps is less than $\textit{c}(\textit{m})(ln$ $\textit{n})\textit{m}(\textit{m}+1);$ Megiddo has shown that, under Smale's model, an upper bound $\textit{C}(\textit{m})$ exists. Thus, for the first time, a polynomial upper bound with no restrictions (except for nondegeneracy) on the problem is proved, and, for the first time, a nontrivial lower bound of precisely the same order of magnitude is established. Both Borgwardt and Smale require the input vectors to be drawn from spherically symmetric distributions. In the model in this paper, invariance is required only under certain ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1985-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 32 Issue Number 4 Page Count 25 Starting Page 871 Ending Page 895

#### Open content in new tab

Source: ACM Digital Library