FEL3350 Network Optimization 4.0 credits

1. Introduction to Network Optimization (L1)

- based on chapter 1 of the course text

- establish terminology and basic notations

- discuss examples of key network models

- provide basics of linear network optimization

2. Shortest path problems (L2)

- based on chapter 2 of the course text

- highlight example application domains

- discuss major methods to address the problem

- discuss the performance of algorithms

3. The Max-Flow problem (L3)

- based on chapter 3 of the course text

- highlight example application domains

- discuss major methods to address the problem

4. The Min-Cost Flow problem (L4)

- based on chapter 4 of the course text

- discuss equivalent variants

- develop duality results in connection with the problem

5.Auction algorithm for Min-Cost Flow (L5)

- based on chapter 7 of the course text

- discuss algorithms design steps

- discuss variants of auction algorithm

6. Network flow arguments for bounding mixing times of Markov chains (L6)

- introduce the concept of mixing time of Markov chains

- conductance bounds and relation to eigenvalues

- multi-commodity flow and the method of canonical paths

7. Accelerated dual descent for network flow optimization (L7)

- review of Newton's method

- approximate Newton method based on network structure

After finishing the course, the attendant will be able to

- describe and explain the basics of linear, non linear, and discrete optimization

- demonstrate and explain the essential properties of network optimization theory

- analyze in depth key network optimization problems

- give detailed descriptions of applications of network optimization to practical engineering problems

- develop a research project and contribute to research frontiers in the area

D. P. Bertsekas, Network Optimization Continuous and Discrete Models, Athena Scientific, Belmont, Mass., USA, 1998.

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

If the course is discontinued, students may request to be examined during the following two academic years.

To pass the course, a passing grade must be achieved for each and every of the following category:

- Attendance: a passing grade is achieved by attending at least two out of seven lectures;

- Homework: a passing grade is achieved by successfully completing two out of five homeworks;

- Course project: a passing grade is achieved by successfully completing the project;

- Final exam: a passing grade is achieved by successfully

Carlo Fischione

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.