The spring semester 2021 will certainly take place online until Easter. Exceptions: Courses that can only be carried out with on-site presence. Please note the information provided by the lecturers.

401-4904-00L  Combinatorial Optimization

SemesterSpring Semester 2019
LecturersR. Zenklusen
Periodicitynon-recurring course
Language of instructionEnglish



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 notesLecture notes will be available online.
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 / NoticePrior exposure to Linear Programming can greatly help the understanding of the material. We therefore recommend that students interested in Combinatorial Optimization get familiarized with Linear Programming before taking this lecture.

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

Courses

NumberTitleHoursLecturers
401-4904-00 VCombinatorial Optimization
takes place in HG G 19.1 with the following exceptions: 21 February, 14 March and 21 March 2019 in HG D 1.2
2 hrs
Thu16-18HG D 1.2 »
16-18HG G 19.1 »
18.04.16-17HG D 1.2 »
16-17HG G 19.1 »
R. Zenklusen
401-4904-00 UCombinatorial Optimization
Starts in the second week of the semester.
1 hrs
Mon14-15HG E 1.2 »
R. Zenklusen

Groups

No information on groups available.

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
Data Science MasterCore ElectivesWInformation
Doctoral Department of MathematicsGraduate SchoolWInformation
Computer Science MasterElective Focus Courses General StudiesWInformation
Computer Science MasterFocus Elective Courses Theoretical Computer ScienceWInformation
Mathematics BachelorSelection: Mathematical Optimization, Discrete MathematicsWInformation
Mathematics MasterSelection: Mathematical Optimization, Discrete MathematicsWInformation
Computational Science and Engineering MasterElectivesWInformation
Statistics MasterStatistical and Mathematical CoursesWInformation