||6 credit points
||Uetz, M. (Universiteit Twente)
||To provide a solid foundation in Discrete Optimization,
with an eye on algorithm design and algorithm analysis,
including the basics of computational complexity.
In Discrete Optimization, as opposed to Continuous Optimization, we deal with objects which are finite or at most countable. An archetypical problem is the notorious traveling salesman problem (find the shortest of a finite number of possible tours), but also linear programming can de seen as a discrete problem (find the 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
• Algorithm Analysis
• Shortest Path Algorithms
• 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
||12 Lectures, Mondays 13:00-14:45 (starting September 21, ending December 7), University of Utrecht,
Take home problems (40%) and a written exam (60%).
The exam will take place on December 14, 2009, 13:00-16:00h in the Blauwe zaal, Wentbuilding, De Uithof, Sorbonnelaan 16, Utrecht.
Re-exam: written or oral (depending on amount of students)
We 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.
- C.H. Papadimitriou and K. Steiglitz: Combinatorial Optimization; Algorithms and complexity, Prentice-Hall, 1982.
- R.K. Ahuja, T.L. Magnanti and J.B. Orlin: Network Fflows, Prentice Hall, 1993.
- T. Cormen, C. Leiserson, R. Rivest and C. Stein: Introduction to Algorithms, 2nd ed., MIT Press, 2001.
- B. Korte and J. Vygen: Combinatorial Optimization - Theory and Algorithms, 4th ed., Springer, 2008.
- V. Vazirani: Approximation Algorithms, Springer-Verlag, 2001
- U. Faigle, W. Kern, and G. Still: Algorithmic Principles of Mathematical Programming, Springer, 2002
Knowledge of linear algebra and basic graph theory is recommended.