Discrete Optimization

Credits	6 credit points
Instructors	Uetz, M. (Universiteit Twente)
E-mail	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 • 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, Mondays 13:00-14:45 (starting September 15, ending December 1), University of Utrecht, Hand-in Excercises
Examination	Written exam (60%), Solutions of Exercises (40%), Re-exam: depending on amount of students, written or oral
Literature	We use selected chapters from • 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 • Ahuja, R. K., T. L. Magnanti, and J. B. Orlin, Network Flows, 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
Prerequisites	BA-level knowledge in Graph Theory and Linear Algebra
Remarks	The written exam will take place on December 15, 2008, 13:00-16:00h Address: Wentgebouw, Groene Zaal de Uithof F.A.F.C.Wentgebouw Sorbonnelaan 16 Tel porter: 030-253 2525 Bus: from cs station lijn 12 (first stop in the Uithof)

Last changed: 18-01-2012 10:21