401-3908-09L Polyhedral Computation
Semester | Spring Semester 2016 |
Lecturers | K. Fukuda |
Periodicity | non-recurring course |
Language of instruction | English |
Abstract | Polyhedral 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. |
Objective | |
Content | In 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: May Szedlák |
Lecture notes | Lecture Notes and Introduction Materials: Link Exercises: Link |
Prerequisites / Notice | This 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 all exercise problems is recommended for a student to be ready for the exam. |