401-4904-00L  Combinatorial Optimization

SemesterSpring Semester 2017
LecturersR. Zenklusen
Periodicityyearly recurring course
Language of instructionEnglish



Courses

NumberTitleHoursLecturers
401-4904-00 VCombinatorial Optimization2 hrs
Thu16:15-18:00ML F 38 »
13.04.16:15-17:00ML F 38 »
R. Zenklusen
401-4904-00 UCombinatorial Optimization
Starts in the second week of the semester.
1 hrs
Mon14:15-15:00HG G 26.5 »
R. Zenklusen

Catalogue data

AbstractCombinatorial 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.
ObjectiveThe 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.
ContentKey topics include:
- Polyhedral descriptions;
- Combinatorial uncrossing;
- Ellipsoid method;
- Equivalence between separation and optimization;
- Design of efficient approximation algorithms for hard problems.
Lecture notesNot available.
Literature- Bernhard Korte, Jens Vygen: Combinatorial Optimization. 5th edition, Springer, 2012.
- Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003. This work has 3 volumes.
Prerequisites / NoticeWe recommend that students interested in Combinatorial Optimization first attend the course "Mathematical Optimization" (401-3901-00L).

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits6 credits
ExaminersR. Zenklusen
Typesession examination
Language of examinationEnglish
RepetitionThe performance assessment is offered every session. Repetition possible without re-enrolling for the course unit.
Mode of examinationoral 30 minutes
Additional information on mode of examinationThe final exam is oral. Furthermore, there is an optional midterm exam that may improve the final grade.
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

 
Main linkCourse Website
Only public learning materials are listed.

Groups

No information on groups available.

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
Doctoral Department of MathematicsGraduate SchoolWInformation
Computer Science MasterFocus Elective Courses Theoretical Computer ScienceWInformation
Mathematics BachelorSelection: Mathematical OptimizationWInformation
Mathematics MasterSelection: Mathematical OptimizationWInformation
Computational Science and Engineering MasterElectivesWInformation
Statistics MasterStatistical and Mathematical CoursesWInformation