# A Simplex Variant Solving An m x d Linear Program in O(min(m squared, d squared)) Expected Number of Pivot Steps

### Ilan Adler, Richard Karp and Ron Shamir

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-83-158

December 1983

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-158.pdf

We present a variant of the Simplex method which requires on the average at most 2(min(m,d)+1)-squared pivots to solve the linear program min cTx, Ax>=b, x>=0 with (A(epsilon)R)mxd. The underlying probabilistic distribution is assumed to be invariant under inverting the sense of any subset of the inequalities. In particular, this implies that under Smale's spherically symmetric model this variant requires an average of no more than 2(d+1)-squared pivots, independent of m, where d<=m.

BibTeX citation:

@techreport{Adler:CSD-83-158, Author = {Adler, Ilan and Karp, Richard and Shamir, Ron}, Title = {A Simplex Variant Solving An m x d Linear Program in O(min(m squared, d squared)) Expected Number of Pivot Steps}, Institution = {EECS Department, University of California, Berkeley}, Year = {1983}, Month = {Dec}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/5951.html}, Number = {UCB/CSD-83-158}, Abstract = {We present a variant of the Simplex method which requires on the average at most 2(min(m,d)+1)-squared pivots to solve the linear program min cTx, Ax>=b, x>=0 with (A(epsilon)R)mxd. The underlying probabilistic distribution is assumed to be invariant under inverting the sense of any subset of the inequalities. In particular, this implies that under Smale's spherically symmetric model this variant requires an average of no more than 2(d+1)-squared pivots, independent of m, where d<=m.} }

EndNote citation:

%0 Report %A Adler, Ilan %A Karp, Richard %A Shamir, Ron %T A Simplex Variant Solving An m x d Linear Program in O(min(m squared, d squared)) Expected Number of Pivot Steps %I EECS Department, University of California, Berkeley %D 1983 %@ UCB/CSD-83-158 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/5951.html %F Adler:CSD-83-158