|
|
Course NP: "Networks and Polyhedra "
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:
Literature:
Examination:
Address of the lecturers:
|
