Courses > PHD Courses
Top image

Management Team
Dutch OR Groups

Landelijk Netwerk Mathematische Besliskunde

Course NP: "Networks and Polyhedra "

Time: Monday 11.00 – 12.45 (November 16 - December 14 and January 25 - February 22).
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 a a number of 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

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

- 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.

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

Dr. L. Sanità
Department of Mathematics and Computer Science
PO Box 513
5600 MB Eindhoven
Phone: 040 2472299