Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 28, 2009, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: David Avis (McGill Univ., Montreal)
A polytopal digraph G(P) is an orientation of the skeleton of a convex polytope P. The possible non-degenerate pivot operations of the simplex method in solving a linear program over P can be represented as a special polytopal digraph known as an LP digraph. Presently there is no general characterization of which polytopal digraphs are LP digraphs, although three necessary properties are well known: acyclicity, unique sink orientation (USO), and the Holt-Klee property. We introduce a fourth property: the shelling property. For each d >= 4 and n >= d+2, we construct a polytopal digraph for a polytope P in dimension d with n vertices which is an acyclic USO that satisfies the Holt-Klee property, but does not satisfy the shelling property. Such examples cannot exist for other values of n and d.
Joint work with H. Miyata and S. Moriyama.
Automatic MiSe System Software Version 1.4803M | admin login