Next: Lecture notes and supplementary Up: Info-page on CGC Block Previous: Course description

# Recommended readings before the lecture

It is very hard to write down specific prerequisites for this course. In a sense it is selfcontained, since we introduce axioms and work with them from scratch. Yet, our axioms, theorems and constructions are often motivated by well-known facts on convex sets and linear optimization problems in Rn. Thus everyone taking this course is highly recommended to review fundamental concepts and theorems on convexity and linear optimization. Also, those with no prior knowledge of complexity theory would profit from reading an introduction to the notions of complexity classes P, NP, co-NP and NP-complete.

• [Convexity and polyhedra] Chapter 1(Basic Properties of Convex Sets) and Chapter 2 (Sections 2.1, 2,2, 2,3) of the book [MS71] by McMullen and Shephard.

Keywords: linear and affine independence, convexity, Helly's theorem, Charathéodory's theorem, convex polytopes and their faces, duality of polytopes.

• [Proof of the upper bound theorem] Kalai's paper [Kal97] contains one of the simplest proofs of the tight upper bound on the number of i-faces of convex polytope with n-facets (or n vertices) in d dimension.

Keywords: convex polytopes and face numbers, f-vector, McMullen's upper bound theorem and proof, simplex method.

Those more computationally oriented may want to look at some additional materials (for Fukuda's part):

• [LP Duality theorem and complexity] The LP duality theorem and Farkas's lemma are two fundamental theorems on linear optimization. There are still many mysteries in the LP theory, in particular, in relation with the question on the existence of ``strongly polynomial algorithms.'' Fukuda's lecture notes [Fuk00b] at ETHZ gives a simple algorithmic proof of these theorems. It also has an introduction to the basic complexity concepts.
• [Polyhedral computation] If you are interested in computation, look at some basic techniques described in Polyhedral Computation FAQ [Fuk98b]. It discusses how one can compute the convex hull, Voronoi diagrams and Delaunay triangulations in Rd. Also ``play with'' some codes [Fuk98a,Fuk00a,BDH95,Avi93].

Next: Lecture notes and supplementary Up: Info-page on CGC Block Previous: Course description
Komei Fukuda
12/14/2000