401-3908-09L  Polyhedral Computation

SemesterFrühjahrssemester 2014
DozierendeK. Fukuda
Periodizitätjährlich wiederkehrende Veranstaltung

KurzbeschreibungPolyhedral computation deals with various computational problems associated with convex polyhedra in general dimension. Typical problems include the representation conversion problem (between halfspace and generator representations), the polytope volume computation, the construction of hyperplane arrangements and zonotopes, the Minkowski addition of convex polytopes.
InhaltIn this lecture, we study basic and advanced techniques for polyhedral computation in general dimension. We review some classical results on convexity and convex polyhedra such as polyhedral duality, Euler's relation, shellability, McMullen's upper bound theorem, the Minkowski-Weyl theorem, face counting formulas for arrangements, Shannon's theorem on simplicial cells. Our main goal is to investigate fundamental problems in polyhedral computation from both the complexity theory and the viewpoint of algorithmic design. Optimization methods, in particular, linear programming algorithms, will be used as essential building blocks of advanced algorithms in polyhedral computation. Various research problems, both theoretical and algorithmic, in polyhedral computation will be presented.

We also study applications of polyhedral computation in combinatorial optimization, integer programming, game theory, parametric linear and quadratic programming.

Teaching assistant: Ms. May Szedlak http://people.inf.ethz.ch/mszedlak/ .
SkriptNotes and Handouts:
Voraussetzungen / BesonderesThis course assumes the basic knowledge of linear programming, which is taught in courses such as "Mathematical Optimization" (401-3901-00L) and "Introduction to Optimization" (401-2903-00L). / Solving at least 50% of exercise problems is required for a student to qualify for the exam.