Linear programming is the problem of minimizing a linear
function f on d variables subject to n linear inequalities. The set of feasible
solutions to a linear programming problem is a polyhedron P whose 0- and
1-dimensional faces (i.e. vertices and edges) define a polytopal graph G.
G can be made directed by orienting every edge in the direction of increasing
function f. Such an orientation is called linearly inducible. The simplex method
solves a linear programming problem by following a path in this directed graph
until the optimum is reached. Understanding the structure of this graph G would
seem necessary to obtain better upper bounds for the simplex algorithm variants
RANDOM-FACET and RANDOM-EDGE.
The following properties are necessary (but not sufficient) for an orientation
to be linearly inducible:
(i) G is acyclic
(ii) Every subgraph of G induced by a non-empty face of P has a unique sink
(and a unique source).
An orientation of a polytopal graph that only satisfies these two properties is
called an Acyclic Unique Sink Orientation (AUSO). Holt and Klee have recently
shown that this far less trivial property is necessary (but again not
sufficient) as well:
(iii) Every subgraph of G induced by a k-dimensional face of P contains k
disjoint paths from source to sink.
An AUSO that satisfies this last property is called a Holt-Klee orientation.
In this talk I will discuss Matousek's sub-exponential lower bounds on AUSOs for
RANDOM-FACET (1994) and for RANDOM-EDGE (2004). I will then discuss Gartner's
1998 result that shows that Matousek's worst case for RANDOM-FACET has
polynomial expected time when orientations are restricted to linearly inducible
ones. No super-polynomial lower bounds have been shown for RANDOM-FACET or
RANDOM-EDGE on a Holt-Klee orientation. Because linearly inducible orientations
are difficult to characterize, one might have a hope that a polynomial upper
bound for either algorithm could be obtained for Holt-Klee orientations. I will
end with Develin's 2002 result that tempers this hope: almost all Holt-Klee
orientations are not linearly inducible.