Course CO1a: "Combinatorial Optimization 1a"

Time:	Monday 13.00 – 14.45 (September 13 – November 8).
Location:	Mathematical Building, Rooms BBL061 (Week 38, 40, 43, 45), BBL023 (Week 39, 42), BBL201 (Week 41, 44), Budapestlaan, Uithof, Utrecht
Lecturer:	Prof.dr. M. Laurent (CWI and Tilburg University).

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 linear programming problems.

The following subjects are discussed:

- Shortest paths and trees.
- Polytopes, polyhedra, Farkas' lemma and linear programming.
- Matchings and covers in bipartite graphs.
- Menger's theorem, flows and circulations.
- Non-bipartite matchings.

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

Literature:
- Lecture notes: A Course in Combinatorial Optimization, A. Schrijver, CWI (chapters 1-5).
- B. Korte and J. Vygen, Combinatorial Optimization, 2e edition, Springer 2001.
- A. Schrijver, Combinatorial Optimization: Polyhedra and efficiency, Volume A: Paths, Flows, Matchings, Springer 2003.

Examination:
Take home problems.

Address of the lecturer:
Prof.dr. M. Laurent
CWI, P.O. Box 94079, 1090 GB Amsterdam.
Phone: 020 - 5924105.
E-mail: m.laurent@cwi.nl