Finishing the example started in the previous lecture — the point is to show how one actually builds a ρ-bounded oracle for a concrete problem.

The LP

  • Minimize Σ_S x_S subject to: for every element e, Σ_{S ∋ e} x_S ≥ 1, and x ≥ 0 (31:53).
  • The convex set is P = { x : x ≥ 0, Σ_S x_S ≤ β } (32:18).
  • MW only answers feasibility, so the objective is folded into P as the budget β: "can I cover at cost ≤ β?" (32:44).
  • With m sets, OPT ∈ [1, m], so β is found by binary search in that range (32:44, 33:13).

Building the oracle

  • Right-hand side: b = 𝟙, so pᵀb = Σ_e p_e = 1 (since p is a distribution). The oracle must decide whether pᵀAx ≥ 1 is achievable (34:28).
  • Rewrite the objective: pᵀAx = Σ_e p_e Σ_{S ∋ e} x_S = Σ_S x_S · p(S), where p(S) := Σ_{e ∈ S} p_e (34:53, 35:14).
  • Since x ≥ 0 with total mass ≤ β, this is (a scaling of) a convex combination of the values p(S) — so it is maximized by dumping all the mass on the single set with the largest p(S) (36:16, 36:43).
  • Oracle rule: pick S* = argmax_S p(S), output x = β · e_{S*} (β times the S*-th standard basis vector), achieving value β · p(S*) (37:03, 37:41, 38:09).
  • If β · p(S*) < 1, report infeasible — the maximum could not reach 1 (38:09, 38:40).

Bounding ρ

For a constraint indexed by element e, examine |a_e·x − b_e| with x = β·e_{S*} (39:10, 39:41):

Casea_e·xViolation magnitude
e ∉ S*01 (40:22)
e ∈ S*ββ − 1 (40:42)
  • So ρ ≤ max(1, β − 1) ≤ β, and since binary search keeps β ∈ [1, m], ρ ≤ m (40:42, 41:18).

Resulting cost

  • Plugging γ = ρ ≤ m into the theorem: O(m² log m / ε²) iterations of multiplicative weights (41:38).
  • The output violates constraints by at most ε; rescaling repairs feasibility at a cost blow-up of roughly (1 + ε), yielding a (1 + ε)-approximate fractional set cover (42:06).

Scope of the general theorem

  • The proof never used non-negativity of A's entries; that assumption only tends to help when implementing oracles (43:02).
  • Having the theorem is not enough — you still must supply a suitable P and an oracle with a good ρ (43:16).
  • Attribution: the approach comes from Plotkin–Shmoys–Tardos (who studied packing/covering LPs); the Arora–Hazan–Kale monograph states the theorem with no packing/covering restriction (43:38, 43:54).