Course NP: "Networks and Polyhedra "

Time:	TBD
Location:	All LNMB courses will be taught on-line until further notice. After registration, students receive a link for the video connection.
Lecturers:	Dr. R. Pendavingh (Eindhoven University of Technology) and Dr. L. Sanità (Eindhoven University of Technology).

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. They arise in a wide variety of applications, e.g. airline crew scheduling, manufacturing, network design, cellular telephone frequency design and optimization problems on graphs.

The course will discuss efficient (polynomial time) algorithms for several fundamental combinatorial optimization problems involving networks. But a focus will be on the geometric viewpoint, which provides a consistent and unifying approach to the subject.

The following subjects will be discussed:

- Polytopes, polyhedra, Farkas' lemma and linear programming
- The geometric viewpoint on combinatorial optimization
- Shortest paths and trees
- Matchings and covers in bipartite graphs
- Menger's theorem, flows and circulations
- Non-bipartite matching

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 and/or oral exam.

Address of the lecturers:
Dr. R. Pendavingh
Department of Mathematics and Computer Science
PO Box 513
5600 MB Eindhoven
Phone: 040 2474235
Email: r.a.pendavingh@tue.nl

Dr. L. Sanità
Department of Mathematics and Computer Science
PO Box 513
5600 MB Eindhoven
Phone: 040 2472299
Email: l.sanita@tue.nl

---