Course CO1b: Combinatorial Optimization 1b

Time:	Monday 13.00 – 14.45 (November 15 - December 13 & January 24 - February 14).
Location:	Mathematical Building, Room 611AB, Budapestlaan, de Uithof, Utrecht
Lecturer:	Dr.ir. C.A.J. Hurkens (TU/e).

Course description:
Combinatorial optimization problems are concerned with the efficient allocation of limited resources to meet desired objectives when the values of the variables are restricted to be integral. Combinatorial problems arise in various applications, e.g. airline crew scheduling, manufacturing, network design, cellular telephone frequency design and optimization problems on graphs. The course deals with polynomial-time solvable combinatorial optimization problems. Many of these problems are special cases of problems that are intrinsically hard to solve - in general.
The following subjects are discussed:
- problems, algorithms and running time; cliques, cocliques and colouring;
- integer linear programming and totally unimodular matrices; multicommodity flows and disjoint paths; matroids.

Literature:
- Lecture notes: A Course in Combinatorial Optimization, A. Schrijver, CWI (chapters 6-10).
- A. Schrijver, Combinatorial Optimization: Polyhedra and efficiency, Volumes A, B, and C, Springer 2003.

Prerequisites:
Basic knowledge (bachelor level) of linear algebra and graph theory.

Examination:
Take home problems.

Address of the lecturer:
Dr.ir. C.A.J. Hurkens
Dept. of Mathematics & Computer Science
Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven
Phone: 040 – 2474771
E-mail: c.a.j.hurkens@tue.nl