SUBJECT
Discrete optimization
lecture + practical
master
3+3
Semesters 1-4
Autumn/Spring semester
Basic notions of graph theory and matroid theory, properties and methods (matchings, flows and circulations, greedy algorithm). The elements of polyhedral combinatorics (totally unimodular matrices and their applications). Main combinatorial algorithms (dynamic programming, alternating paths, Hungarian method). The elements of integer linear programming (Lagrangian relaxation, branch-and-bound).
András Frank: Connections in combinatorial optimization (electronic notes).
Further reading:
- W.J. Cook, W.H. Cunningham, W.R. Pulleybank, and A. Schrijver, Combinatorial Optimization, John Wiley and Sons, 1998.
- B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2000.
- E. Lawler, Kombinatorikus Optimalizálás: hálózatok és matroidok, Műszaki Kiadó, 1982. (Combinatorial Optimization: Networks and Matroids).
- A. Schrijver, Combinatorial Optimization: Polyhedra and efficiency, Springer, 2003. Vol. 24 of the series Algorithms and Combinatorics.
- R. K. Ahuja, T. H. Magnanti, J. B. Orlin: Network flows: Theory, Algorithms and Applications, Elsevier North-Holland, Inc., 1989