SUBJECT

Title

Discrete optimization

Type of instruction

lecture + practical

Level

master

Part of degree program
Credits

3+3

Recommended in

Semesters 1-4

Typically offered in

Autumn/Spring semester

Course description

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).

Readings

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