Linear and Network Optimization - Kathrin Klamroth
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
Last Update: July 1, 2003 - Kathrin Klamroth - klamroth@am.uni-erlangen.de