- français
- English
Coursebooks
Combinatorial optimization
MATH-460
Lecturer(s) :
Language:
English
Remarque
pas donné en 2019-20Summary
The guiding question of Combinatorial Optimization is: How do I efficiently select an optimal solution among a finite but very large set of alternatives? We will address the solution of this question in the context of classical discrete optimization problems.Content
- Paths and flows: Stronlgly polynomial time algorithms for shortest paths and minimum cost network flows
- Minimum spanning trees and matroids: Greedy, Kruskal's and Prim's algorithm
- Arborescences and matroid intersection
- Polyhedra and approximation algorithms
- Maximum weight matchings in general graphs and the matching polytope
Keywords
- Algorithm
- Polyhedron
- Matroid
- NP-completeness
Learning Prerequisites
Required courses
Discrete optimization (Second year math.)
Learning Outcomes
By the end of the course, the student must be able to:- Choose an appropriate method for solving a combinatorial optimization problem
- Prove theorems in discrete optimization
- Design algorithms
- Analyze efficiency of algorithms
Transversal skills
- Demonstrate a capacity for creativity.
- Continue to work through difficulties or initial failure to find optimal solutions.
- Assess one's own level of skill acquisition, and plan their on-going learning goals.
Teaching methods
Ex cathedra lecture and exercises to be solved at home and in the classroom
Expected student activities
Attendance of lectures and exercises
Completion of exercises at home
Study of literature
Assessment methods
Written exam during exam session
Supervision
Office hours | Yes |
Assistants | Yes |
Forum | No |
Resources
Bibliography
Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag.
In the programs
- SemesterFall
- Exam formWritten
- Credits
5 - Subject examined
Combinatorial optimization - Lecture
2 Hour(s) per week x 14 weeks - Exercises
2 Hour(s) per week x 14 weeks
- Semester
- SemesterFall
- Exam formWritten
- Credits
5 - Subject examined
Combinatorial optimization - Lecture
2 Hour(s) per week x 14 weeks - Exercises
2 Hour(s) per week x 14 weeks
- Semester
- SemesterFall
- Exam formWritten
- Credits
5 - Subject examined
Combinatorial optimization - Lecture
2 Hour(s) per week x 14 weeks - Exercises
2 Hour(s) per week x 14 weeks
- Semester
- SemesterFall
- Exam formWritten
- Credits
5 - Subject examined
Combinatorial optimization - Lecture
2 Hour(s) per week x 14 weeks - Exercises
2 Hour(s) per week x 14 weeks
- Semester
- SemesterFall
- Exam formWritten
- Credits
5 - Subject examined
Combinatorial optimization - Lecture
2 Hour(s) per week x 14 weeks - Exercises
2 Hour(s) per week x 14 weeks
- Semester
- SemesterFall
- Exam formWritten
- Credits
5 - Subject examined
Combinatorial optimization - Lecture
2 Hour(s) per week x 14 weeks - Exercises
2 Hour(s) per week x 14 weeks
- Semester
- SemesterFall
- Exam formWritten
- Credits
5 - Subject examined
Combinatorial optimization - Lecture
2 Hour(s) per week x 14 weeks - Exercises
2 Hour(s) per week x 14 weeks
- Semester
Reference week
Mo | Tu | We | Th | Fr | |
---|---|---|---|---|---|
8-9 | |||||
9-10 | |||||
10-11 | |||||
11-12 | |||||
12-13 | |||||
13-14 | |||||
14-15 | |||||
15-16 | |||||
16-17 | |||||
17-18 | |||||
18-19 | |||||
19-20 | |||||
20-21 | |||||
21-22 |
Lecture
Exercise, TP
Project, other
legend
- Autumn semester
- Winter sessions
- Spring semester
- Summer sessions
- Lecture in French
- Lecture in English
- Lecture in German