Consider the following simple random process, on a 3-dimensional bounded convex polyhedron, with a given starting vertex: Repeatedly choose a random edge that goes "down" (decreasing the z-coordinate), and follow it to the vertex at the other end -- if there are several choices, pick one of them, with equal probability. Stop once you have reached a vertex with minimal z-coordinate.

We investigate the worst-case behavior of the simplex algorithm on linear programs with three variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we consider, the "random edge" rule yields the best asymptotic behavior as well as the most complicated analysis. All other rules turn out to be much easier to study, but also produce worse results: Most of them show essentially worst-possible behavior; this includes both Kalai's "random-facet" rule, which without dimension restriction is known to be subexponential, and Zadeh's deterministic history-dependent rule, for which no nonpolynomial instances in general dimensions have been found so far.

In this paper we modify Buchberger's S-pair reduction algorithm for computing a Gröbner basis of a toric ideal so as to apply it to an integer program (IP) in inequality form with fixed right-hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented, and we give elementary proofs for their correctness. A relationship among these (exact) algorithms, iterative improvement heuristics, and the Kernighan--Lin procedure is established. Computational results are also presented.

W'e give a lower bound of 0( ~ldt2j ) for the number of vertices of ad-dimensional polytope with ffacetswllich canappear on the outer boundary of a projection to dimension 2 < k < d.By duality, this implies a lower bound of Q( n ld\2j ) for the number of facets in a k-dimensional slice of a d-dimensional polytope with n vertices. .

We investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes (1972) and similar linear programs with exponential decreasing paths. The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus we disprove two bounds conjectured in the literature. At the same lime, we establish quadratic upper bounds for random pivots on the linear programs under investigation. This motivates the question whether some randomized pivot rules possibly have quadratic worst-case behavior on general linear programs.>