Linear and Network Optimization - Kathrin Klamroth

Linear and Network Optimization
Kathrin Klamroth, Summer Term 2003

Wednesday 08:15 - 09:45 in the small auditorium, and
Wednesday, 02.07.03: Übungsraum III
Thursday 14:15 - 15:45 in the large auditorium, Bismarckstr.
Start of classes: 09.04.2003
End of classes: 03.07.2003


Prerequisits: Linear Algebra I and II


Literature:

H.W. Hamacher and K. Klamroth:
"Lineare und Netzwerk-Optimierung / Linear and Network Optimization".
Bilingual textbook, Vieweg, 2000.

C.H. Papadimitriou and K. Steiglitz:
"Combinatorial Optimization: Algorithms and Complexity".
Prentice-Hall, 1982.

M.S. Bazaraa, J.J. Jarvis and H.D. Sherali:
"Linear Programming and Network Flows", 2. edition.
Wiley, 1990.

R.K. Ahuja, T.L. Magnanti and J.B. Orlin:
"Network Flows: Theory, Algorithms and Applications".
Prentice-Hall, 1993.


Outline:

Part I: Linear Optimization.
1. Introduction: Linear programs and their applications
2. The simplex method
3. Duality; primal-dual simplex method
4. Interior point methods

Part II: Network Optimization.
5. Introduction to graph theory; shortest spanning trees
6. Shortest path problems
7. Network flow problems and the network simplex algorithm
8. Matchings


Homework and course material:

ps-files: pdf-files:
Homework 1 (09.04.03): homework1.ps homework1.pdf
Homework 2 (16.04.03): homework2.ps homework2.pdf
Homework 3 (23.04.03): homework3.ps homework3.pdf
Handout 1 (24.04.03): handout1.ps handout1.pdf
Handout 2 (30.04.03): handout2.ps handout2.pdf
Homework 4 (30.04.03): homework4.ps homework4.pdf
Solution to Problem 4.4: solution4-4.ps solution4-4.pdf
Handout 3 (07.05.03): handout3.ps handout3.pdf
Homework 5 (07.05.03): homework5.ps homework5.pdf
Handout 4 (08.05.03): handout4.ps handout4.pdf
Homework 6 (14.05.03): homework6.ps homework6.pdf
Handout 5 (21.05.03): handout5.ps handout5.pdf
Homework 7 (21.05.03): homework7.ps homework7.pdf
Homework 8 (28.05.03): homework8.ps homework8.pdf
Handout 6 (04.06.03): handout6.ps handout6.pdf
Homework 9 (04.06.03): homework9.ps homework9.pdf
Homework 10 (11.06.03): homework10.ps homework10.pdf
Handout 7 (18.06.03): handout7.ps handout7.pdf
Homework 11 (18.06.03): homework11.ps homework11.pdf
Homework 12 (26.06.03): homework12.ps homework12.pdf
Homework 13 (02.07.03): homework13.ps homework13.pdf


Questions!? Mail to: klamroth@am.uni-erlangen.de


This information in German


Last Update: July 1, 2003 - Kathrin Klamroth - klamroth@am.uni-erlangen.de