| Lecturer: | Andreas Karrenbauer |
| Assistant: | Martin Niemeier |
| Course Language: | English |
| Exercise Language: | English |
News
- 23.09.2009: Details to the grading and bonus system have been revealed. See grading and examination section.
- 03.09.2009: There will be an introductory lecture on monday, 14.09.2009, instead of the exercise session (17:15 – 19:00, room MAA330).
- 03.09.2009: The first exercise sheet has been released. It can be found in the courses subversion repository at https://svn.epfl.ch/svn/coopt-autumn-2009/. You have access to the repository as soon as you have joined the coopt-autumn-2009 group.
- 17.07.2009: A group for this lecture called coopt-autumn-2009 has been created. If you participate in the course, please join this group here.
Description
This lecture will cover a selection of problems in Combinatorial Optimization. On this basis, the students will learn the relation between polyhedra and efficiency. This involves correctness proofs and objective is to enhance the mathematical modelling skills of the students to enable them to recognize and exploit combinatorial optimization problems in broader contexts. Weekly theoretical and practical take-home assignments will monitor the learning progress of the students. As a side effect, they will learn the foundations of Algorithm Engineering and Algorithm Library Design.
Topics
- Paths and Trees (Connectivity, Shortest Path, Minimum Spanning Tree)
- Cycles, Flow, and Cuts (Negative Cycles, Minimum Mean Cycles, Max Flow, Min Cut, Min Cost Network Flow)
- Cycles and Flows (Negative Cycles, Minimum Mean Cycles, Max Flow, Min Cost Network Flow)
- Matchings (Bipartite, Non-bipartite)
Prerequisites
- Linear programming
- Basic knowledge of C++
Grading and Examination
There will be a written exam at the end of the semester. Bonus points will be awarded for active participation during the semester.
Your final grade gets computed with the following formula:
where p is the percentage of points obtained in the exam and b is the percentage of bonus points collected during the semester. ceil is a function that rounds the argument up to the nearest integer.
Bonus points can be collected by handing in written solutions for the exercises (or submitting solutions to programming exercises to the SVN). Per exercise, up to 2 bonus points can be obtained.
Time and Date
Lecture: Wednesdays, 14:15 – 16:00, MAA330
Exercise session: Mondays, 17:15 – 19:00, MAA330
Assignment sheets and exercise sessions
Every week there will be an assignment sheet with exercises covering the topics discussed in the lecture. Your are highly encouraged to work on these exercises on your own or in small groups. The assignment sheets are accessible via a subversion repository located at https://svn.epfl.ch/svn/coopt-autumn-2009/. You have access to the repository as soon as you have joined the coopt-autumn-2009 group using this link.
The solutions to the exercises will be discussed in the exercise sessions one week after the sheet was released.
You can hand in written solutions during the exercise sessions to receive feedback from the TA.