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 20 |
syllabus,
the Konigsberg
bridges problem, eulerian tour, shortest path (SP), max
flow (MF), and min cost flow (MCF) problems
|
Scb1
|
Vid1
|
| 2 |
Aug 22 |
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 |
Aug 27 |
seat-sharing
problem, assignment problem, network definitions,
(in/out)degree, adjacency lists, induced and spanning subgraphs
|
Scb3
|
Vid3
|
| 4 |
Aug 29 |
walk, (directed) path, \(pred(i)\), (strongly) connected,
(spanning) tree, cuts, node-arc incidence matrix, node-node
adjacency matrix
|
Scb4
|
Vid4
|
| 5 |
Sep 3 |
forward star representation, (r)point
vector, Matlab session and
commands, network transformations: removing lower bounds
|
Scb5
|
Vid5
|
| 6 |
Sep 5 |
arc reversal, removing finite upper bounds (gives bipartite
graph), node splitting, computational complexity: algorithm
running time
|
Scb6
|
Vid6
|
| 7 |
Sep 10 |
\(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 12 |
breadth/dept-first search (BFS/DFS), complexity of search:
\(O(m)\) time, reverse search, strong connectivity,
topological order
|
Scb8
|
Vid8
|
| 9 |
Sep 17 |
topological order, \(O(m)\) algo for topological order, flows
along paths and cycles, flow decomposition into
\(\leq m+n\) paths+cycles
|
Scb9
|
Vid9
|
| 10 |
Sep 19 |
shortest path (SP) problem: assumptions, bead-string analogy,
knapsack problem as SP, UPDATE\((i)\) step, Dijkstra's
algorithm
|
Scb10
|
Vid10
|
| 11 |
Sep 24 |
correctness of Dijkstra's algo, properties of shortest paths,
complexity of Dijkstra: \(O(n^2)\) time, reverse and
bidirectional Dijkstra
|
Scb11
|
Vid11
|
| 12 |
Sep 26 |
Dial's implementation of Dijkstra, buckets, SP optimality
conditions, generic label-correcting (LC) algo, finiteness,
modified LC algo
|
Scb12
|
Vid12
|
| 13 |
Oct 1 |
complexity of modified LC algo, FIFO implementation: \(O(mn)\)
time, detecting negative cycles, problems from
the practice midterm
|
Scb13
|
Vid13
|
| 14 |
Oct 3 |
Midterm exam
|
| 15 |
Oct 8 |
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 10 |
matrix rounding problem as MF; residual network
\(G(\mathbf{x})\), \(r_{ij} = u_{ij} - x_{ij}+x_{ji}\),
augmenting path (AP), generic AP algorithm
|
Scb16
|
Vid16
|
| 17 |
Oct 15 |
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 17 |
MFMC and network reliability, pathological instance of generic
AP algo, shortest augmenting path (SAP) algo: distance labels
\(d(i)\)
|
Scb18
|
Vid18
|
| 19 |
Oct 22 |
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 24 |
\(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 |
Oct 29 |
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 |
Oct 31 |
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
|
| 23 |
Nov 5 |
Min-cost flow (MCF) assumptions, residual network for MCF,
negative cycle optimality conditions, negative cycle canceling
algo
|
Scb23
|
Vid23
|
| 24 |
Nov 7 |
reduced cost optimality cdtns, complementary slackness cdtns,
successive shortest path (SSP) algo, pseudoflow,
\(\mathbf{\pi}'=\mathbf{\pi}-\mathbf{d}\)
|
Scb24
|
Vid24
|
| 25 |
Nov 12 |
SSP algo steps, example, minimum spanning trees (MSTs), tree
and non-tree arcs, cut and path optimality condidions for MST
|
Scb25
|
Vid25
|
| 26 |
Nov 14 |
Kruskal's & Prim's algos for MST, UNION-FIND,
bipartite cardinality matching, simple networks,
assignment,SSP for assignment
|
Scb26
|
Vid26
|
| 27 |
Nov 19 |
video: stable marriage, unstable pair, propose and
reject algorithm, group 1-optimal matching, non-bipartite
cardinality matching
|
Scb27
|
Vid27
|
| 28 |
Nov 21 |
video: alternating/augmenting paths, augmentation \(M
\oplus P\), \(G'=(N,M \oplus M^*)\) components, unmatched node
in max matching
|
Scb28
|
Vid28
|
| 29 |
Dec 3 |
relabel bottleneck case in SAP algo, a method to generate
random networks in layers (for project)
|
Scb29
|
Vid29
|
Last modified: Sun Dec 08 23:48:27 PST 2024
|