Skip to main content
Skip header

Combinatorial Optimization

Summary

Many problems of everyday (industrial) practice are de facto optimization
problems: in a set of feasible solutions (e.g., assigning tasks to workers or
processors, scheduling of trucks and their routes, design of layout of
electronic components at printed circuit boards) we search for a solution that
is optimal in some respect (like cost, time). These problems can be often
formulated as problems of combinatorial (or discrete) optimization, mostly in
the terms of graphs and (integer) linear inequalities. Some problems can be
satisfactorily solved by quick polynomial algorithms, at others (NP-hard
problems) we have to be satisfied with algorithms that only approximate
optimal solutions, or with other (heuristic) algorithms that give reasonable
outcomes though their quality is not guaranteed generally.
The goal of the course is to explain the area of combinatorial optimization,
the classification of problems that belong here, and the methods used for
their solving in practice.

Literature

Jon Lee: A first course in combinatorial optimization, Cambridge
University Press, 2004

Advised literature

- Bernhard Korte, Jens Vygen: Combinatorial Optimization (Theory and Algorithms), Springer (5th edition 2012)

- Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization:
Algorithms and Complexity, Dover Publications, 1998.

- Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice, Morgan Kaufmann, 2004.

- Alexander Schrijver: Combinatorial Optimization (3 volume, A,B, & C),
Springer, 2003.


Language of instruction čeština, angličtina
Code 460-4091
Abbreviation KO
Course title Combinatorial Optimization
Coordinating department Department of Computer Science
Course coordinator doc. Ing. Zdeněk Sawa, Ph.D.