Go to main content

PDF

Description

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.

Details

Files

Statistics

from
to
Export
Download Full History
Formats
Format
BibTeX
MARCXML
TextMARC
MARC
DublinCore
EndNote
NLM
RefWorks
RIS