Polyhedral Computation         Autumn 2012

Prof. David Avis                  Lecture summaries and links       Announcements                     Course home page


Prerequisite:

A basic knowledge of linear programming is assumed.


Assessment:

Grading Methods and Evaluation Criteria:    

1. The course grade is based on 3 reports with due on dates: Thurs. Nov 1,   Thurs. Dec 6,   Thurs. Jan. 10  in class.
2. Each report will be graded pass/fail.

 3. Final grades:  A: 3 passes,   B: 2 passes,  C: 1 pass,   No Credit: 0 passes.

 4. S grade will be given for student who gets an A and also solves optional bonus problems.


Topics:   Subject to revision.

The following topics are covered, each in one to three lectures.
1.Examples of polyhedral computation problems arising in various fields.
2.Basic problems in polyhedral computation.
3.Polyhedral problems solvable by linear programming.
4.The vertex enumeration problem and its relatives.
5.Algorithms for vertex enumeration.
6.Applications to game theory, triangulations, Voronoi diagrams, etc.
7.Connections with integer programming.

Teaching Assistant:           Atsuki Nagao        a-nagao  at lab2.kuis.kyoto-u.ac.jp


October 1, 2012