The analytic engine of the primal-dual framework (1:12:14).

Statement

Let x, y be feasible solutions to the primal and dual respectively — feasible meaning they satisfy all constraints, not that they are optimal (1:12:53, 1:14:05).

Recall the primal: minimize cᵀx s.t. Ax ≥ b, x ≥ 0 (1:12:53).

Suppose there exist α, β > 0 such that (1:13:29, 1:14:05, 1:14:53):

  • Primal condition: for all i, if x_i > 0 then the corresponding dual constraint is nearly tight: c_i/α ≤ (Aᵀy)_i ≤ c_i (the upper bound is just dual feasibility).
  • Dual condition: for all i, if y_i > 0 then the corresponding primal constraint is nearly tight: b_i ≤ a_i · x ≤ β·b_i.

Then cᵀx ≤ α·β·bᵀy (1:15:32).

Proof is pure definition-chasing and was assigned to homework (1:15:32, 1:16:06).

Why it gives an approximation guarantee

Chain the inequalities (1:16:44, 1:17:11, 1:17:39, 1:17:58):

bᵀy  ≤  OPT_dual  ≤  OPT_primal        (y feasible; weak duality)
cᵀx  ≤  α·β·bᵀy   ≤  α·β·OPT_primal    (the lemma)

So the constructed x is within a factor α·β of optimal (1:17:58).

Practical reading

If you can construct any pair of feasible primal/dual solutions satisfying these slackness conditions, you immediately get a bound on how close your solution is to OPT — the point of the lemma is to give control over your competitive ratio, not to be elegant (1:16:06, 1:18:16, 1:18:50).

flowchart TD
  A["Build feasible primal x<br/>online"] --> C{"Check α, β<br/>slackness"}
  B["Build feasible dual y<br/>online"] --> C
  C -->|"cᵀx ≤ αβ·bᵀy"| D["Competitive ratio αβ"]