UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


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

Archive Home Page

A Family of Simplex Variants Solving An m x d Linear Program in Expected Number of Pivot Steps Depending on d Only

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

Abstract: We present a family of variants of the Simplex method, which are based on a Constraint-By-Constraint procedure: the solution to a linear program is obtained by solving a sequence of subproblems with an increasing number of constraints. We discuss several probabilistic models for generating linear programs. In all of them the underlying distribution is assumed to be invariant under changing the signs of rows or columns in the problem data. a weak regularity condition is also assumed. Under these models, for linear programs with d variables and m+d inequality constraints, the expected number of pivots required by these algorithms is bounded by a constant when the number of constraints tends to infinity. Since Smale's original model [S1] satisfies our probabilistic assumptions, the same results apply to his model. We also present some results for models generating only feasible linear programs, and for Bland's pivoting rule. We conclude with a discussion of our probabilistic models, and show why they are inadequate for obtaining meaningful results unless d and m are of the same order of magnitude.