Topics of Combinatorial Optimization
Objectives
Development of knowledge, skills and competences to address a wide variety of combinatorial optimization problems.
General characterization
Code
11643
Credits
6.0
Responsible teacher
Jorge Orestes Lasbarrères Cerdeira
Hours
Weekly - 4
Total - 42
Teaching language
Português
Prerequisites
Available soon
Bibliography
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.
Teaching method
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 periods of service pre-established, assimilates the theoretical material and seeks to solve the suggested exercises.
During the semester there will be one test and the presentation of a work on a specific topic. The student can choose to be approved on a final exam.
Evaluation method
During the semester there will be one test and the presentation of a work on a specific topic. The student can choose to be approved on a final exam.
Subject matter
1. Graphs
2. Polytopes
3. Matchings and covers in bipartite graphs
4. Flows
5. Matroids
6. Computational complexity
7. Integer linear programming and totally unimodular matrices
Programs
Programs where the course is taught: