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

Last modified: Fri Dec 09 16:20:17 PST 2016