Network Optimization - Lecture Notes and Videos

Math 566  - Lecture Notes and Videos on Network Optimization

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, shortest path (SP), max flow (MF), and min cost flow (MCF) problems, scribe video
2 Aug 25 optimization model for MCF, flow balance, SP as MCF, circulation problem, MF as MCF, transportation problem, seat sharing problem scribe video
3 Aug 30 assignment problem, more on seat sharing, tips for network formulations, definitions: adjacency lists, subgraphs (induced/spanning), walk scribe video
4 Sep   1 pred$$(i)$$, acyclic graph, strongy connected, spanning tree, cut, node-arc and node-node incidence matrices, forward star representation scribe video
5 Sep   6 point vector, octave code (and output) to create $$A(i), AI(i)$$ lists, network transformations: removing nonzero lower bounds, arc reversal scribe video
6 Sep   8 removing upper bounds, node splitting, complexity of algorithms, running time and space limits, $$O(\cdot), \Omega(\cdot), \Theta(\cdot)$$ notation scribe video
7 Sep 13 polynomial and strongly/pseudo polynomial time algorithms, generic search, admissible arc, marking nodes, breadth-first search (BFS) scribe video
8 Sep 15 depth-first search (DFS), complexity of search is $$O(m)$$, reverse search, checking strong connectivity, topological ordering scribe video
9 Sep 20 example of topological ordering, flow in arcs $$x_{ij}$$ vs flow in paths and cycles, intermediate flow $$\mathbf{y}$$, flow decomposition algorithm scribe video
10 Sep 22 bfs code tips, octave session, flow decomposition theorem, shortest path problem (SPP), assumptions, string analogy, knapsack problem scribe video
11 Sep 27 UPDATE$$(i)$$ step, Dijkstra's algorithm, illustration, distance label $$d(i)$$, properties of shortest paths, correctness of Dijkstra's algorithm scribe video
12 Sep 29 correctness of Dijkstra, complexity of Dijkstra's algorithm: $$O(n^2)$$, reverse and bidirectional Dijkstra, Dial's implementation, buckets scribe video
13 Oct   4 video review for midterm (posted on 09/30), problems from the practice midterm exam scribe video
14 Oct   6 midterm exam
15 Oct 11 shortest path optimality conditions: $$d(j) \leq d(i) + c_{ij}$$, generic label correcting algo, proof of finiteness, modified label correcting algo scribe video
16 Oct 13 FIFO label correcting algo, detecting negative cycles, reduced costs, all-pairs SP optimality conditions, optimization model for MF scribe video
17 Oct 18 assumptions for MF, applications of MF, residual network $$G(\mathbf{x})$$, residual capacity, augmenting path, generic augmenting path algorithm scribe video
18 Oct 20 recovering $$x_{ij}$$ from optimal $$r_{ij}$$, finiteness of augmenting path algo, $$s$$-$$t$$ cut, flow and capacity of cut, max-flow min-cut theorem (MFMC) scribe video
19 Oct 25 network reliability: arc- and node-disjoint paths using MFMC, pathological example, shortest augmenting path (SAP) algo, admissible path scribe video
20 Oct 27 exact distance labels, details of SAP algo, advance and retreat operations, example of SAP, correctness of SAP, complexity - outline scribe video
21 Nov  1 SAP complexity $$O(n^2m)$$: details, capacity scaling, $$G(\mathbf{x},\Delta)$$, $$\Delta$$-maximum flow, complexity of capacity scaling $$O(nm \log U)$$, preflow scribe video
22 Nov  3 generic preflow-push algo, water pipe analogy, example, FIFO implementation, example, excess scaling algorithm, large excess nodes scribe video
23 Nov  8 Min-Cost Flow (MCF), assumptions, residual network, reduced costs, negative cycle optimality conditions, negative cycle canceling algo scribe video
24 Nov 10 cycle canceling algo: example, finiteness, complexity, reduced cost optimality, economic interpretation, complementary slackness (CSC) scribe video
25 Nov 15 CSC: $$c_{ij}^{\pi} = 0 \not\Rightarrow 0 < x_{ij} < u_{ij}$$, successive shortest path algo, pseudoflow, imbalance, excess, deficit, $$\boldsymbol{\pi} = \boldsymbol{\pi} - \mathbf{d}$$ preserves optimality scribe video
26 Nov 17 minimum spanning trees (MST), cut and path optimality conditions, Kruskal's algo, complexity: $$O(m \log n)$$, union-find, Prim's algo scribe video
27 Nov 29 union-find example, bipartite cardinality matching as max flow on a simple network, weighted bipartite matching (assignment) problem scribe video
28 Dec   1 relaxation algo for assignment, stable marriage problem, unstable pair, propose-and-reject algo, man-optimal matching, complexity scribe video
29 Dec   6 nonbipartite cardinality matching, alternating and augmenting path, symmetric difference, augmenting $$M \oplus P$$, components of $$M \oplus M^*$$, scribe video
30 Dec   8 make-up lecture for snow day: note on SAP algo, generating valid random networks for max flow problems (project) scribe video