ISSN:
1432-5217
Keywords:
Key words: Linear programming
;
average-case complexity of algorithms
;
stochastic geometry
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s186-1999-8373-5
Permalink
