1. Introduktion till nätverksoptimering (L1)
- baseras på kap 1 i kursboken
- grundläggande terminologi och notation
- diskutera exempel på nätverksoptimering
- grunderna i linjär nätverksoptimering
2. "Shortest path problems" (L2)
- baseras på kap 2 i kursboken
- exempel på tillämpningsområden
- vanliga verktyg för att lösa problemet
- lösningsalgoritmernas prestanda
3. Maximala flödesproblem (L3)
- baseras på kap 3 i kursboken
- exempel på tillämpningsområden
- vanliga verktyg för att lösa problemet
4. Kostnadsminimering av flöden (L4)
-baseras på kap 4 i kursboken
- ekvivalenta varianter
- utveckla resultat inom dualitet i samband med problemet
5. Auktionsalgoritmer för kostnadsminimering av flöden (L5)
- baseras på kap 7 i kursboken
- steg för algoritmdesign
- varianter av auktionsalgoritmer
6. Flödesargument för begränsning av blandningstider för Markovkedjor (mixing time) (L6)
- introduktion av konceptet blandningstider för Markovkedjor
- begränsningar av konduktansen och relationen till egenvärden
- varuflöden och "method of canonical path"
7. "Accelerated dual descent" för flödesoptimering (L7)
- Newtons metod
- Approximativ Newtons metod baserad på nätverkets struktur