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
|