2012HS: 53003 Combinatorial Optimization

Optimization problems often involve many simple and interrelated decisions which – combined - yield a set of feasible solutions that is finite, but astronomically large. Applications are numerous, e.g. finding optimal paths or tours in a road network, determining cost optimal production and distribution in a supply chain, scheduling tasks, assigning personnel, etc. Combinatorial optimization deals with modeling and solving such problems, and a core of standard problems, models (often related to graphs), and methods has developed. In this course, we address some of these standard problems, including optimal trees in graphs and independent sets in matroids, maximum and minimum cost flows in networks, maximal and optimal matchings in bipartite and general graphs, optimal postman tours, traveling salesman tours, maximum stable sets and minimum colorings. Literature (mandatory): Cook J. C., Cunningham W. H., Pulleyblank W. R., Schrijver, A., Combinatorial Optimization, Wiley-Interscience 1998 Further recommended: - Lee, J., A First Course in Combinatorial Optimization, Cambridge University Press, 2004 - Korte B., Vygen J., Combinatorial Optimization: Theory and Algorithms, 4th Ed., Springer, Berlin, 2007