On bad linear programs

Günter Ziegler
Technische Universität Berlin

How does a typical linear program look like, and how does a
bad linear program look like - for a specific randomized
pivot rule?

In this lecture, I plan to report about three studies:
-- on bad 3-dimensional linear programs for RANDOM_EDGE and RANDOM_FACTS,
(joint work with Volker Kaibel, Rafael Mechtel, and Micha Scharir)
-- on RADOM_EDGE and RANDOM_FACET on Klee-Minty cubes
(joint work with Bernd Gärtner), and
-- on RANDOM_SHADOW projections of "real-life" linear programs
(joint work with S. Fischer)

Presentation (PDF File)

Back to Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?