Math 466/566: Lecture Notes and Videos on Network Optimization
|
Copyright: I (Bala Krishnamoorthy) hold the copyright
for all lecture scribes/notes, documents, and other
materials including videos posted on these course web
pages. These materials might not be used for commercial
purposes without my consent.
|
Scribes from
all lectures so far (as a single big file)
| Lec | Date | Topic(s) | Scribe | Video |
| 1 |
Aug 25 |
syllabus,
the Konigsberg
bridges problem, Eulerian tour, shortest path (SP), max
flow (MF), and min cost flow (MCF) problems
|
Scb1
|
Vid1
|
| 2 |
Aug 27 |
MCF as optimization model, SP as MCF, MF as MCF: \((t,s)\)
with \(c_{ts}=-1,u_{ts}=\infty\), transportation
problem, seat-sharing problem
|
Scb2
|
Vid2
|
| 3 |
Sep 1 |
seat-sharing
problem, assignment problem, network definitions,
(in/out)degree, adjacency lists, induced and spanning subgraphs
|
Scb3
|
Vid3
|
| 4 |
Sep 3 |
walk, (directed) path, pred\((i)\), (strongly) connected,
(spanning) tree, cuts, node-arc incidence and node-node
adjacency matrices
|
Scb4
|
Vid4
|
| 5 |
Sep 8 |
forward star representation, (r)point
vector, Matlab
session and commands, network transformations:
removing lower bounds
|
Scb5
|
Vid5
|
| 6 |
Sep 10 |
arc reversal, removing upper bounds (gives bipartite
graph), node splitting, computational complexity:
algorithm running time
|
Scb6
|
Vid6
|
| 7 |
Sep 15 |
\(O(f(n)), \Omega(f(n)), \Theta(f(n))\) for running time and
functions, problem size, polynomial & exponential time algos,
generic search
|
Scb7
|
Vid7
|
| 8 |
Sep 17 |
video: breadth/dept-first search (BFS/DFS),
complexity of search: \(O(m)\), reverse search, strong
connectivity, topological order
|
Scb8
|
Vid8
|
| 9 |
Sep 22 |
topological order, indegree updates, \(O(m)\)
algorithm for topological order, flows along paths and
cycles, flow
decomposition
|
Scb9
|
Vid9
|
| 10 |
Sep 24 |
flow decomp theorem, shortest path (SP), assumptions,
bead-string model, knapsack as SP, UPDATE\((i)\) step,
Dijkstra's algorithm
|
Scb10
|
Vid10
|
| 11 |
Sep 29 |
Dijkstra example, correctness of Dijkstra, properties
of SPs, complexity of Dijkstra: \(O(n^2)\) time,
reverse and bidirectional Dijkstra
|
Scb11
|
Vid11
|
| 12 |
Oct 1 |
Dial's implementation of Dijkstra, buckets, SP optimality
conditions, generic label-correcting (LC) algo, finiteness,
modified LC algo
|
Scb12
|
Vid12
|
| 13 |
Oct 6 |
complexity of modified LC algo, FIFO implementation:
\(O(mn)\) time, detecting negative cycles, problems
from practice
midterm
|
Scb13
|
Vid13
|
| 14 |
Oct 8 |
midterm
|
| 15 |
Oct 13 |
all pairs SP (APSP), reduced costs, \(c_{ij}^{\mathbf{d}} =
c_{ij} + d(i) -d(j)\), APSP optimality conditions, maximum
flow (MF), feasible flow as MF
|
Scb15
|
Vid15
|
| 16 |
Oct 15 |
matrix rounding problem as max flow; residual network
\(G(\mathbf{x})\), \(r_{ij} = u_{ij} - x_{ij}+x_{ji}\),
augmenting path (AP), generic AP algorithm
|
Scb16
|
Vid16
|
| 17 |
Oct 20 |
finiteness of AP algo, \(s\)-\(t\) cut \([S,\bar{S}]\), flow
across & capacity of cut, \(F_{\mathbf{x}}[S,\bar{S}] \leq
U[S,\bar{S}]\), max-flow min-cut (MFMC) theorem, proof
|
Scb17
|
Vid17
|
| 18 |
Oct 22 |
MFMC and network reliability, pathological instance of generic
AP algo, shortest augmenting path (SAP) algo: distance labels
\(d(i)\)
|
Scb18
|
Vid18
|
| 19 |
Oct 27 |
exact \(d(i)\)'s, \(d(i)\) as height of \(i\) above ground, SAP
algo, illustration, proof of correctness: \(d(i)\)'s remain
valid after augmentation
|
Scb19
|
Vid19
|
| 20 |
Oct 29 |
\(d(i)\) valid after relabel, complexity of SAP: \(O(n^2m)\),
time for relabels: \(O(nm)\), capacity scaling algo,
\(G(\mathbf{x},\Delta)\), \(\Delta\)-maximal flow
|
Scb20
|
Vid20
|
| 21 |
Nov 3 |
complexity of capacity scaling: \(O(m^2 \log U)\),
preflow, excess \(e(i)\), active node: \(e(i) > 0\),
generic preflow-push algo, example
|
Scb21
|
Vid21
|
| 22 |
Nov 5 |
tips for implementing SAP: arc predecessor, FIFO preflow-push
algo, run time \(O(n^3)\), pushing flow back to \(s\), excess
scaling algo
|
Scb22
|
Vid22
|
Last modified: Thu Nov 05 16:47:29 PST 2026
|