The LP relaxation and its dual

Primal (4:23):

  • minimize sum_S c_S * x_S
  • subject to sum_{S : i in S} x_S >= 1 for all i = 1..n
  • and x_S >= 0 for all S

Dual (6:31):

  • maximize sum_{e=1..n} y_e
  • subject to sum_{e in S} y_e <= c_S for all sets S
  • and y >= 0

"An" LP relaxation, not "the" LP relaxation

  • Prompted by a student question, the lecturer corrects himself: a problem has many LP relaxations, because it has many integer-program formulations (4:49).
  • Set cover is the primal above with x_S in {0,1}; relaxing that constraint to a linear inequality is only one choice, and a different formulation could give better results (4:49).
  • There is a systematic way to produce successively tighter LP relaxations of an integer program: the Sherali-Adams hierarchy (pointer only, not covered in the course) (5:26, 5:45).
  • Eventually the hierarchy reproduces the integer program exactly — but by then the LP has blown up to exponential size (6:08).

The dual fitting scheme

Maintain a dual solution while building the primal (7:00). When greedy takes a set S (7:37):

  1. Set x_S = 1.
  2. For each element e newly covered by S, set y_e = c_S / (number of elements newly covered by S) — i.e. y is a price vector, each newly covered element paying its share (12:40).

Why this works

  • Weak duality: for any feasible primal/dual pair, dual cost <= OPT <= primal cost (8:32, 8:52).
  • The catch: this y need not be dual-feasible. The fix is to scale it down entry-wise — dividing by roughly log n makes it feasible (8:52).

Observations (9:09):

  • The primal cost of x equals the dual cost of y — the scheme is rigged that way.
  • y / H_n is feasible for the dual (H_n = the n-th harmonic number).
  • The primal x is feasible because the while-loop runs as long as a constraint is violated (9:48).
  • Together these imply the log n approximation (9:48).

Proof of the claim: y / H_n is dual feasible

Only the constraint sum_{e in S} y_e <= c_S * H_n can be violated; non-negativity is automatic (10:25, 10:55).

  1. Fix a set S of size K; order its elements e_1, ..., e_K by when they were first covered (10:55, 11:41).
  2. Right before e_i was covered, S had not yet been chosen, so greedy could have chosen S at price c_S / (K - i + 1) — since at least K - i + 1 of its elements were still uncovered (12:55, 13:34).
  3. Greedy always picks the lowest available price, so price(e_i) <= c_S / (K - i + 1) (14:06).
  4. Summing: sum_{e in S} y_e <= c_S * sum_{i=1..K} 1/i = c_S * H_K (14:28).

Note that e_i may be covered by some other set, not by S — the argument only needs an upper bound on the price actually charged (12:22, 12:40).

The stronger corollary

  • K = |S| <= n, so the bound gives H_n (14:56).
  • Stronger result proved along the way: if every set in the set system has size at most K, greedy is an H_K (i.e. log K) approximation (14:56).