Topics of Combinatorial Optimization
Development of knowledge, skills and competences to address a wide variety of combinatorial optimization problems.
Isabel Cristina Silva Correia
Weekly - Available soon
Total - 56
Knowledge of Linear Programming and of basics of Graph Theory.
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2012.
L. Lovász and M.D. Plummer, Matching Theory, North-Holland Mathematics Studies, 1986.
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
D.B. West, Introduction to Graph Theory, Prentice Hall, 2001
The course consist of lectures where presentations of theoretical concepts, proofs, and resolution and discussion of proposed exercises are conducted; and study outside the classroom, where the student, individually and in groups, using the available material and the support of teachers, in classes and in pre-established office hours, assimilates the theoretical material and seeks to solve the suggested exercises.
During the semester there will be two tests and one work on a specific topic.
3. Matchings and covers in bipartite graphs
6. Computational complexity
7. Integer linear programming and totally unimodular matrices