Coursebooks

Combinatorial optimization

MATH-460

Lecturer(s) :

Language:

English

Remarque

pas donné en 2019-20

Summary

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.