Courses > Master Courses
Top image

 
Home
News & announcements
Courses
Management Team
Conferences
Dutch OR Groups
People
Links
Contact
 

Landelijk Netwerk Mathematische Besliskunde

Course DO: "Discrete optimization"

 
Time: Monday 13.00 - 14.45 (September 21 - December 7)
Location: Minnaert Building, Room 211, Leuvenlaan 4, Utrecht (Uithof): September 21 - November 2 AWK (Aardwetenschappen Kleine zaal), Budapestlaan 4, Utrecht (Uithof): November 9 - December 7
Lecturer: Prof.dr. M. Uetz (UT)

Aim
To provide a solid foundation in Discrete Optimization, with an eye on algorithm design and algorithm analysis, including the basics of computational complexity.

Course 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

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.
- 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.

Prerequisites:
Knowledge of linear algebra and basic graph theory is recommended.

Examination:
Take home problems (40%) and a written exam (60%) on December 14, 13:00-16.00h, Blauwe zaal, Wentbuilding, Sorbonnelaan16, De Uithof, Utrecht.
Re-exam written or oral (depending on amount of students).

Addres of the lecturer:
Prof.dr. M. Uetz
Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede
Phone: 053-4893420; E-mail: m.uetz@math.utwente.nl; URL: http://wwwhome.math.utwente.nl/~uetzm/home.html