Math 566: Lecture Notes and Videos on Network Optimization

Scribes from all
lectures so far (as a single
**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.
**big** file)

Lec # Date Topic(s) Scribe Panopto
1
Aug 23
syllabus,
the Konigsberg
bridges problem, eulerian tour, shortest path (SP), max flow
(MF), and min cost flow (MCF) problems
Scb1
Vid1
2
Aug 25
MCF (
*updated*) as optimization model, flow balance, SP as
MCF, MF as MCF: \((t,s)\) with \(c_{ts}=-1,u_{ts}=\infty\),
transportation problem
Scb2
Vid2
3
Aug 30
seat-sharing
problem, assignment problem, network definitions,
(in/out)degree, adjacency lists, induced and spanning subgraphs
Scb3
Vid3
4
Sep 1
walk, (directed) path, \(pred(i)\), (strongly) connected,
(spanning) tree, cuts, node-arc incidence matrix, node-node
adjacency matrix
Scb4
Vid4
5
Sep 6
forward star representation, (r)point vector, Matlab session and
commands, network transformations: removing lower bounds
Scb5
Vid5
6
Sep 8
arc reversal, removing finite upper bounds (gives bipartite
graph), node splitting, running time of algorithm \(T(n)\) is
\(O(f(n))\)
Scb6
Vid6
7
Sep 13
\(O(f(n)), \Omega(f(n)),\) and \(\Theta(f(n))\), problem size,
poly- and exp-time algos, generic search, breadth- and
depth-first search (BFS/DFS)
Scb7
Vid7
8
Sep 15
full example on BFS, and on DFS, complexity of search: \(O(m)\)
time, DFS identifies cycles quickly, reverse search, strong
connectivity
Scb8
Vid8
9
Sep 20
topological order, flows along paths and
cycles, flow decomposition algo,
flow decomposition theorem, at most \(m+n\) paths & cycles
Scb9
Vid9
10
Sep 22
shortest path (SP) problem: assumptions, bead-string analogy of
SP, knapsack problem as SP, UPDATE\((i)\) step, Dijkstra's
algorithm
Scb10
Vid10
11
Sep 27
(
*make-up*)
correctness of Dijkstra, properties of shortest paths,
complexity of Dijkstra: \(O(n^2)\) time, reverse and
bidirectional Dijkstra
Scb11
Vid11
12
Sep 29
(
*make-up*)
Dial's implementation, buckets, SP optimality conditions,
generic label-correcting (LC) algo, finiteness, modified LC algo
Scb12
Vid12
13
Oct 4
complexity of modified LC algo, FIFO implementation: \(O(mn)\)
time, detecting negative cycles, problems from
the practice midterm
Scb13
Vid13
14
Oct 6
midterm exam
15
Oct 11
all pairs shortest paths (APSP), reduced costs,
\(c_{ij}^{\mathbf{d}} = c_{ij} + d(i) -d(j)\), APSP optimality
conditions, max flow (MF), feasible flow as MF
Scb15
Vid15
16
Oct 13
matrix rounding as MF; residual network \(G(\mathbf{x})\),
\(r_{ij} = u_{ij} - x_{ij}+x_{ji}\), augmenting path (AP),
generic AP algo, optimal \(x_{ij}\)'s from \(G(\mathbf{x})\)
Scb16
Vid16
17
Oct 18
finiteness of AP algo, \(s\)-\(t\) cut \([S,\bar{S}]\), flow
across and capacity of a cut, \(F_{\mathbf{x}}[S,\bar{S}] \leq
U[S,\bar{S}]\), max-flow min-cut (MFMC) theorem, proof
Scb17
Vid17
18
Oct 20
MFMC and network reliability, pathological instance of generic
AP algo, shortest augmenting path (SAP) algo: distance labels
\(d(i)\)
Scb18
Vid18
19
Oct 25
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 27
\(d(i)\)'s are 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 1
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 3
FIFO preflow-push algo, run time \(O(n^3)\), pushing flow back
to \(s\), excess scaling algo, min-cost flow (MCF) assumptions:
feasibility
Scb22
Vid22
23
Nov 8
more assumptions for MCF, residual network for MCF, reduced
cost, negative cycle optimality conditions, negative cycle
canceling algo
Scb23
Vid23
24
Nov 10
reduced cost optimality conditions, complementary slackness
conditions, successive shortest path (SSP) algo, pseudoflow,
\(\mathbf{\pi}'=\mathbf{\pi}-\mathbf{d}\)
Scb24
Vid24
25
Nov 15
(
*make-up*)
example of SSP algo, minimum spanning trees (MSTs), tree and
non-tree arcs, cut and path optimality condidions for MST
Scb25
Vid25
26
Nov 17
(
*make-up*) Kruskal's & Prim's
algos, UNION-FIND,
bipartite cardinality matching, simple networks, assignment, SSP
for assignment
Scb26
Vid26
27
Nov 29
stable marriage problem, unstable pair, propose and reject
algorithm, group 1-optimal matching, non-bipartite cardinality
matching
Scb27
Vid27
28
Dec 1
alternating and augmenting paths, augmentation \(M \oplus P\),
components of \(G'=(N,M \oplus M^*)\), unmatched node in maximal
matching
Scb28
Vid28
29
Dec 6
relabel bottleneck case in SAP algo, a method to generate random
networks in layers (for project)
Scb29
Vid29

Last modified: Tue Dec 06 20:47:17 PST 2022