Advanced Algorithms (COMPSCI 224), Lecture 20

Harvard University · 1:23:37 · https://www.youtube.com/watch?v=TdTFYVjzs1I

A two-part lecture. The first half closes out multiplicative weights by showing how it approximately solves linear programs: the m LP constraints become the "experts", a ρ-bounded oracle answers a one-constraint relaxation each day, and the average of the oracle's answers is an almost-feasible point. Fractional set cover is worked through end to end as a concrete instantiation. The second half opens a new topic, max flow — the definitions, the LP formulation and what interior point methods buy for it, and finally Ford–Fulkerson with residual graphs and augmenting paths.

flowchart TD
    subgraph MW["Part 1 — Multiplicative weights (finishing up)"]
        T1["1. MW recap & regret"] --> T2["2. LP feasibility + ρ-bounded oracle"]
        T2 --> T3["3. MW for LPs: theorem & proof"]
        T3 --> T4["4. Worked example: fractional set cover"]
    end
    subgraph FL["Part 2 — Flows (new topic)"]
        T5["5. Max flow: definitions & LP"] --> T6["6. Solving max flow via LP machinery"]
        T6 --> T7["7. Ford–Fulkerson"]
    end
    T4 --> T5
    T7 --> NEXT["Next lecture: faster flow algorithms"]

Topics

  1. Multiplicative weights recap and regret
  2. LP feasibility and the ρ-bounded oracle
  3. Multiplicative weights for LPs: theorem and proof
  4. Worked example: fractional set cover
  5. Max flow: definitions and LP formulation
  6. Solving max flow with LP machinery
  7. Ford–Fulkerson: augmenting paths and residual graphs

Key takeaways

  • Given a ρ-bounded oracle with ρ > ε/2, multiplicative weights returns x ∈ P with Ax ≥ b − ε·𝟙 in O(ρ² log m / ε²) iterations — the LP's m constraints play the role of experts and the output is the average of the oracle's per-iteration answers (15:41, 29:29).
  • The proof is a squeeze: the oracle's guarantee forces ⟨m_t, p_t⟩ ≥ 0 while the MW regret bound caps it from above; choosing η = ε/(2γ) and T = 4γ² ln m / ε² makes both error terms ε/2 (22:29, 27:32, 28:35).
  • For fractional set cover the oracle is trivial — put all β mass on the set maximizing p(S) = Σ_{e∈S} p_e — which gives ρ ≤ β ≤ m and hence O(m² log m / ε²) MW iterations for a (1+ε)-approximate solution, with β found by binary search over [1, m] (37:03, 41:18, 41:38, 42:06).
  • Max flow is exactly an LP, and a generic interior point method solves it in about O(m^{3.5} L) because each of the √m Newton steps is a linear system solve costing m³ (53:21, 1:00:31).
  • Exploiting flow structure beats the generic bound twice over: Daitch–Spielman (STOC 2008) solve the flow-induced (Laplacian-like) systems in Õ(m), giving m^{3/2} log² U, and Lee–Sidford's weighted barrier turns the √m iteration count into √n, giving m√n (1:01:44, 1:02:43, 1:04:39).
  • Ford–Fulkerson's O(m · f*) scales with the flow value, not the graph size — a small graph with billion-scale capacities can force ~a billion steps — and its correctness rests on: f* is maximum iff s and t are disconnected in the residual graph G_{f*} (1:05:32, 1:06:35, 1:21:21).