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