UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-83-158.pdf
Oskicat catalog record
Conditions of Use

Archive Home Page

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

Authors:
Adler, Ilan
Karp, Richard
Shamir, Ron
Technical Report Identifier: CSD-83-158
December 1983
CSD-83-158.pdf

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.