
Discrete Optimization
Credits 
6 credit points 
Instructors 
Uetz, M. (Universiteit Twente) 
Email 
m.uetz@utwente.nl 
Aim 
To provide a solid foundation in Discrete Optimization, with an eye on algorithm design and algorithm analysis, including the basics of computational complexity. 
Description 
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 treated
• Algorithm Analysis • Shortest Path Algorithms • Spanning Trees & Matroids • Maximum Flows & Minimum Cuts • Minimum Cost Flows • P, NP, coNP, NPcompleteness • Integer Linear Programming & Total Unimodularity • Approximation Algorithms • PrimalDual Algorithms • Inapproximability & Approximation Schemes 
Organization 
12 Lectures, Mondays 13:0014:45 (starting September 21, ending December 7), University of Utrecht, Handin Excercises 
Examination 
Take home problems (40%) and a written exam (60%). The exam will take place on December 14, 2009, 13:0016:00h in the Blauwe zaal, Wentbuilding, De Uithof, Sorbonnelaan 16, Utrecht. Reexam: written or oral (depending on amount of students) 
Literature 
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, PrenticeHall, 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, SpringerVerlag, 2001  U. Faigle, W. Kern, and G. Still: Algorithmic Principles of Mathematical Programming, Springer, 2002 
Prerequisites 
Knowledge of linear algebra and basic graph theory is recommended. 
