| About Mastermath |
| Courses & exams |
| Program & schedule |
| Registration & other forms |
| Links |
| Locations |
| Contact |
|
Discrete Optimization
| Credits | 6 credit points |
| Instructors | Schäfer, G. (CWI) |
| g.schaefer@cwi.nl | |
| Aim | The aim of the course is to provide a solid foundation in Discrete Optimization. A particular focus will be given to the design and analysis of algorithms and to computational complexity. |
| Description | Discrete Optimization is about the problem of finding a best solution among a set of feasible solutions. The set of feasible solutions might be astronomically large but is assumed to be discrete (finite or countably infinite), which also constitutes the major difference to Continuous Optimization. A notorious example is the traveling salesman problem, where we are asked to find a shortest tour among all tours that visit every node of a given graph exactly once. Yet another example is linear programming, which can be interpreted as the problem of finding a best among a finite number of vertices of a polyhedron. The course introduces some of the most relevant problems from the area, as well as algorithms to solve them. The following topics will (most probably) be treated • Introduction to Algorithms & Analysis • Shortest Path Algorithms • Minimum Spanning Trees & Matroids • Maximum Flows & Minimum Cuts • Minimum Cost Flows • P, NP, coNP, NP-completeness • Integer Linear Programming & Total Unimodularity • Approximation Algorithms • Primal-Dual Algorithms • Inapproximability & Approximation Schemes |
| Organization | 12 lectures (2h + 5x4h + 2h), every second Monday (alternating with Continuous Optimization), Hand-in Exercises. Dates: September 19, 2011 (13:15-15:00) |
| Examination | Take home problems (40%) and a written exam (60%) |
| Literature | We will use a reader with selected chapters from several books listed below. The reader can be purchased in the first lecture. Occasionally additional copies will be distributed (if necessary). • W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley, 1998. ISBN 0-471-55894-X • C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization; Algorithms and Complexity, Prentice-Hall, 1982. ISBN 0-13-152462-3 • Ahuja, R. K., T. L. Magnanti, and J. B. Orlin, Network Flows, Prentice Hall, 1993. ISBN 0-13-617-549. • T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001. ISBN10 0262531968 • B. Korte and j. Vygen, Combinatorial Optimization - Theory and Algorithms, 4th ed., Springer, 2008. ISBN10 3-540-25684-9. |
| Prerequisites | Knowledge of linear algebra and graph theory is advantageous. |
| Remarks | Course page: More information and study material can be found athttp://homepages.cwi.nl/~schaefer/courses/lnmb-do11/main.html |