Network Optimization: Lecture Notes and Videos

Math 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 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