• Overview: Metrics and Guarantees
• Set Cover: Greedy ln n-approx
• Vertex Cover: 2-approx via Matching
• LP Relaxations, Rounding, and Primal–Dual
• Hardness and Limits
• Exercises

• Approximation ratio α(n): alg cost ≤ α(n) · OPT (minimization) or ≥ OPT/α(n) (maximization).
• PTAS: for any ε>0, runs poly(n) for fixed ε and returns (1+ε)-approx.
• FPTAS: poly(n, 1/ε) time. Exists for some problems (e.g., knapsack), not for others unless P=NP.

// Universe U, collection S = [S0, S1, ...] subsets of U. Optional weights w[i] >= 0.
function greedySetCover(U, S, w = []) {
  const n = U.length; const Uset = new Set(U);
  const chosen = []; const covered = new Set();
  const weights = w.length ? w : S.map(() => 1);
  while (covered.size < n) {
    let best = -1, bestScore = Infinity, bestGain = 1;
    for (let i = 0; i < S.length; i++) {
      const gain = S[i].reduce((c, x) => c + (!covered.has(x) ? 1 : 0), 0);
      if (gain === 0) continue;
      const score = weights[i] / gain; // cost-effectiveness
      if (score < bestScore) { bestScore = score; bestGain = gain; best = i; }
    }
    if (best === -1) throw new Error('Uncoverable element: instance infeasible');
    chosen.push(best);
    for (const x of S[best]) covered.add(x);
  }
  return chosen; // indices of chosen sets
}

• Guarantee: H(d)-approx where d is max set size; ≤ H(n) ≤ ln n + 1.
• Idea: pick set with best cost-per-newly-covered element at each step.
• Weighted case: same greedy by cost-effectiveness achieves ln n approximation.

// 2-approx: take endpoints of edges in any maximal matching
function approxVertexCover(n, edges) {
  const adj = Array.from({length: n}, () => new Set());
  for (const [u,v] of edges) { adj[u].add(v); adj[v].add(u); }
  const used = Array(n).fill(false);
  const inCover = Array(n).fill(false);
  for (let u = 0; u < n; u++) if (!used[u]) {
    for (const v of adj[u]) if (!used[v]) { // pick edge (u,v)
      used[u] = used[v] = true; inCover[u] = inCover[v] = true; break;
    }
  }
  return inCover; // boolean array
}

• Why 2? Any matching has ≤ OPT edges; we take 2 vertices per matching edge.
• Weighted case: LP relaxation + rounding or primal–dual gives 2-approx.

• Set cover LP: minimize Σ w_i x_i s.t. for each element e: Σ_{i:e∈S_i} x_i ≥ 1, x_i ≥ 0. Round via randomized rounding or primal–dual.
• Vertex cover LP: minimize Σ w_v x_v s.t. x_u + x_v ≥ 1 for each edge (u,v), x ≥ 0. Round by thresholding x_v ≥ 1/2.
• Dual fitting/primal–dual: grow dual variables until constraints become tight to pick sets/vertices.

• Set cover: cannot be approximated within (1−o(1))·ln n unless P=NP.
• Vertex cover: under UGC, hardness ~1.36; best known approx ratio ~2−Θ(1/√log n) for special cases.

1. Implement greedy set cover (weighted and unweighted) and test the ln n bound empirically.
2. Implement the 2-approx vertex cover via maximal matching; compare vs. optimal on small graphs.
3. Formulate LPs for both problems and try randomized rounding; compare solutions.