Combinatorial Optimization
Code
10809
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Jorge Orestes Cerdeira
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
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 available from http://homepages.cwi.nl/~lex/files/dict.pdf
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2008
L.A. Wolsey, Integer Programming, Wiley, 1998.
Teaching method
In this course classes are theoretical-practical.
Lectures consist of expose of theoretical concepts and carry up some proffs, using the framework and the projector, and resolution of exercises and problems.
Part of the study is done independently by the student, individually and in groups, using bibliographic brackets, and the support of the teacher in the classroom, and in pre-established schedules reserved for the students'''' attendence.
Evaluation method
The student will be excluded of the evaluation if his presences in classes is less than 2/3 of the total number of classes.
The student can be evaluated by two tests (each counts 5), and a written and oral presentation of a study on a proposed (to be defined latter) subject (counting 10). Student will be approved if the results ontained in the three evaluation elements sum up (rounded) at least 10. The grade will be the rounded sum.
The student can also be approved by a final exam if the exam''''s grade is at least 10. The grade will be the one attained in the exam (rounded).