Combinatorial Optimization

Main content

Lecturer Assistant Lecture Exercise
Prof. Dr. Rico Zenklusen

Andrea Baggio,

Simon Bruggmann

Martin Nägele

 

Thu 16-18

HG G 26.1

Mon 14-15

HG G 26.5

Short description

Combinatorial Optimization deals with efficiently finding a provably strong solution among a finite set of options. This course discusses key combinatorial structures and techniques to design efficient algorithms for combinatorial optimization problems. We put a strong emphasis on polyhedral methods, which proved to be a powerful and unifying tool throughout combinatorial optimization.

Prerequisites

This is an advanced optimization course that builds upon "Mathematical Optimization" (401-3901-00L), which is a prerequisite for taking this lecture.

Main objective

The goal of this lecture is to get a thorough understanding of various modern combinatorial optimization techniques with an emphasis on polyhedral approaches. Students will learn a general toolbox to tackle a wide range of combinatorial optimization problems.

Content

The core topics of this lecture include:

  • Polyhedral descriptions of combinatorial problems
  • Combinatorial uncrossing
  • Ellipsoid Method
  • Equivalence between separation and optimization
  • Design of efficient approximation algorithms for hard problems (if time permits)

Bibliography

  • Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012.
  • Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes.

Grading

The final exam is oral. Furthermore, there is an optional midterm exam that may improve the final grade.

Moodle

Lecture notes, problem sets, and further information will be made available through the moodle page of this course.

 
 
Page URL: https://www.math.ethz.ch/ifor/education/courses/spring-2016/combinatorial-optimization.html
26.04.2017
© 2017 Eidgenössische Technische Hochschule Zürich