Combinatorial Optimization
Code
10809
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Isabel Cristina Silva Correia
Weekly hours
4
Teaching language
Português
Objectives
(i) Comprehension of the main concepts from graphs, polyhedra and matroids
(ii) Development of algorithm designing skills
(iii) Improving modeling skills
(iv) Improving mathematical maturity
Prerequisites
Students are supposed to have knowledge in Linear Programming, and some skills in algorithms.
Subject matter
1. Graphs
2. Modeling with binary variables
3. Integer programming
4. Trees
5. Shortest paths
6. Matchings
7. Flows
8. Matroids
9. Computational complexity
10. Approximation algorithms
Bibliography
L.A. Wolsey, Integer Programming, Wiley, 1998.
D.B. West, Introduction to Graph Theory, Prentice Hall, 2001
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Springer, 2003
A. Schrijver, A Course in Combinatorial Optimization, 2013
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2008
rithms