There are two types of pivot algorithms for linear programming. The first one traces
the LP digraph, the graph of the feasible region oriented by the objective function. An
algorithm of this type is often called a simplex method. The second type follows the graph of
the arrangement of hyperplanes in which the feasible region is just one cell. The criss-cross
method is of this second type, and let us call an algorithm of the second type an arrangement
method.
In this talk, we look at the differences of the two approaches from various view points,
including the diameters of the associated graphs, the existence of short sequences of admissible
pivots, polynomially solvable special cases, etc. We also look at a surprising fact
shown by Hazan and Megiddo in 2007 that the phase I of the simplex method can be set
up so that it traces the arrangement graph. This means that the existence of a strongly
polynomial simplex method for this phase I implies the strongly polynomial solvability of
linear programming, but does not imply a polynomial bound for the diameters of convex
polyhedra.
Finally, we consider the randomized criss-cross method which selects a random ordering
of the variables at the beginning. We conjecture that the randomized criss-cross method
is an expected strongly polynomial method for linear programming and convex quadratic
programming.
Copyright. All Rights Reserved.