A lower bound on the average number of Pivot-steps for solving linear programs Valid for all variants of the Simplex-Algorithm

Karl Heinz Borgwardt and Petra Huhn

Mathematical Methods of Operations Research, 1999, vol. 49, issue 2, 175-210

Abstract: In this paper we derive a lower bound on the average complexity of the Simplex-Method as a solution-process for linear programs (LP) of the type: We assume these problems to be randomly generated according to the Rotation-Symmetry-Model: *Let a 1 ,…,a m , v be distributed independently, identically and symmetrically under rotations on ℝ n \{0}. We concentrate on distributions over ℝ n with bounded support and we do our calculations only for a subfamily of such distributions, which provides computability and is representative for the whole set of these distributions. The Simplex-Method employs two phases to solve such an LP. In Phase I it determines a vertex x 0 of the feasible region – if there is any. In Phase II it starts at x 0 to generate a sequence of vertices x 0 ,… ,x s such that successive vertices are adjacent and that the objective v T x i increases. The sequence ends at a vertex x s which is either the optimal vertex or a vertex exhibiting the information that no optimal vertex can exist. The precise rule for choosing the successor-vertex in the sequence determines a variant of the Simplex-Algorithm. We can show for every variant, that the expected number of steps s var for a variant, when m inequalities and n variables are present, satisfies This result holds, if the selection of x 0 in Phase I has been done independently of the objective v. Copyright Springer-Verlag Berlin Heidelberg 1999

Keywords: Key words: Linear programming; average-case complexity of algorithms; stochastic geometry (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s186-1999-8373-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:49:y:1999:i:2:p:175-210

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s186-1999-8373-5

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().