Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
9 Probabilistic Analysis in Linear Programming
9 Probabilistic Analysis in Linear Programming
Pages 131-148
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 131... ...
9.1 The Linear Programming Problem The linear programming (LP) problem cads for minimizing a linear objective function subject to linear constraints.
|
From page 132... ...
of dimension ~-1 and is called a facet of the polyhedron. The simplex method starts from a feasible vertex, and moves in each iteration to an adjacent vertex, until eventually either an optimal vertex is reached or the algorithm recognizes at some vertex that the problem is unbounded.
|
From page 133... ...
However, by the early 1970s it became clear that the simplex is not as far as we know a theoretically efficient algorithm: the complexity of the simplex method was shown to be finite, but not polynomial in the input length. In fact, on specially structured "bad" examples, many simplex variants were shown to require a number of pivots exponential in the problem dimensions.
|
From page 134... ...
9.2.1 Parametric Simplex Variants The variant of the simplex that has been proved most amenable to probabilistic analysis is the parametric objective simplex algorithm, due to Gass and Saaty (1955~. This variant- explicitly or in disguise plays a central role in most of the studies discussed below.
|
From page 135... ...
, so this algorithm avoids the need for two simplex phases. The convenience in analyzing the parametric simplex is due to its property that, given a vertex of the feasible set, one can determine directly if the simplex path passes through that vertex.
|
From page 136... ...
also obtained interesting asymptotic upper and lower bounds for several specific spherically symmetric distributions.
|
From page 137... ...
Following Smale, Blair (1986) showed that essentially the same asymptotic result can be obtained by a simpler argument, under somewhat weaker probabilistic assumptions.
|
From page 138... ...
In particular, when ~ is fixed and m j oo, the expected number of steps is bounded by a constant. By using more efficient CBC alga rithms and stronger probabilistic assumptions, the upper bound is reduced to a smaller function of al, but it still remains exponential.
|
From page 139... ...
and Haimovich (1983) studied independently the expected number of pivots along paths generated by some parametric simplex variants.
|
From page 140... ...
There are striking examples from linear complementarily theory (Megiddo, 1986b; Saigal, 1983) where a path starting from a random point has expected polynomial length and a path starting at a fixed point has expected exponential length.
|
From page 141... ...
observed that, although the parametric CBC algorithm and the PSD algorithm are in genera] quite different, their lexicographic versions execute exactly the same sequence of pivots.
|
From page 142... ...
(1992) and extended to cover a fairly general class of convex programming problems, to a dual simplex algorithm with Of n · 23)
|
From page 143... ...
showed that a careful analysis of the previous randomized simplex algorithm of Sharir and WeIz!
|
From page 144... ...
, A family of simplex variants solving an m x ~ linear program in expected number of pivots depending on c! only, Math.
|
From page 145... ...
, Parallel linear programming in fixed dimension almost surely in constant time, in Proc. 31st IEEE Symposium on the Foundations of Computer Science, {EKE Computer Society Press, I'os Alam~tos, Calif., 574-582.
|
From page 146... ...
, A randomized algorithm for fixeddimensional linear programming, Math. Programming 44, 202-212.
|
From page 147... ...
(1991) , Low dimensional linear programming and convex hulls made easy, Discrete Comput.
|
From page 148... ...
(1986) , Polynomial expected behavior of a pivoting algorithm for linear complementary and linear programming problems, Math.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.