Greedy Approximations

The simplest approximation technique: make locally optimal choices and prove the total cannot be too far off.

Set cover — $H_n\approx \ln n$

Repeatedly take the set covering the most uncovered elements.

vector<int> greedySetCover(int n, vector<vector<int>>& sets) {
    vector<bool> covered(n, false);
    vector<int> chosen;
    int remaining = n;
    while (remaining > 0) {
        int best = -1, bestGain = 0;
        for (int i = 0; i < (int)sets.size(); i++) {
            int gain = 0;
            for (int e : sets[i]) if (!covered[e]) gain++;
            if (gain > bestGain) { bestGain = gain; best = i; }
        }
        if (best < 0) break;                              // infeasible
        for (int e : sets[best]) if (!covered[e]) { covered[e] = true; remaining--; }
        chosen.push_back(best);
    }
    return chosen;
}

The analysis. When an element is covered, charge it $\frac{1}{\text{gain}}$ of that set’s cost. If OPT uses $k$ sets, then at any point some set covers at least $\frac{\text{remaining}}{k}$ elements, so the charge to each element is at most $\frac{k}{\text{remaining}}$. Summing gives $k{H}_n$. ∎

This is optimal: no polynomial algorithm achieves $(1-\epsilon )\ln n$ unless P=NP (Dinur-Steurer, 2014).

Vertex cover — 2

vector<int> vertexCover2(vector<pair<int,int>>& edges) {
    vector<bool> in(n, false);
    vector<int> cover;
    for (auto [u, v] : edges) {
        if (in[u] || in[v]) continue;
        in[u] = in[v] = true;                             // take BOTH endpoints
        cover.push_back(u); cover.push_back(v);
    }
    return cover;
}

Taking both endpoints is what makes the proof work: the chosen edges form a matching, OPT must cover each of them with $\ge 1$ vertex, so $\mathrm{OPT}\ge |M|$ and $\mathrm{ALG}=2|M|$.

The "obvious" greedy is worse

Repeatedly taking the highest-degree vertex feels better but is only $\Theta (\log n)$-approximate — there are constructions where it does much worse than 2. Counterintuitive, and a good reminder that intuition is not a proof.

The catalogue

Problem	Greedy rule	Ratio
Set cover	most uncovered elements	$\ln n$
Weighted set cover	best cost per new element	$\ln n$
Vertex cover	both endpoints of an uncovered edge	2
Metric TSP	double the MST	2
Metric TSP	Christofides	1.5
Max cut	move any vertex that improves the cut	2 (i.e. $\ge \frac{1}{2}$)
Makespan	least-loaded machine	$2-\frac{1}{m}$
Makespan	LPT (longest first)	$\frac{4}{3}-\frac{1}{3m}$
Bin packing	First-Fit-Decreasing	$\frac{11}{9}\mathrm{OPT}+\frac{6}{9}$
$k$-center	farthest-point (Gonzalez)	2
Max coverage ($k$ sets)	most new elements	$1-\frac{1}{e}\approx 0.63$
Steiner tree	MST of the metric closure	2
Knapsack	ratio order + best single item	2

The $1-1/e$ barrier

Max coverage (pick $k$ sets maximising coverage) has greedy ratio $1-\frac{1}{e}$, and this is optimal unless P=NP. The same constant appears for submodular maximisation under a cardinality constraint (Nemhauser-Wolsey-Fisher) — a broad and genuinely useful theorem:

Greedy is $(1-\frac{1}{e})$-optimal for maximising any monotone submodular function subject to a cardinality constraint.

Submodularity (“diminishing returns”: $f(S\cup \{x\})-f(S)$ shrinks as $S$ grows) covers coverage, influence spread, sensor placement, and feature selection.

Farthest-point clustering ($k$-center)

// pick k centers; each new center is the point farthest from all chosen so far
centers.push_back(0);
for (int i = 1; i < k; i++) {
    int far = argmax over p of (min distance to a chosen center);
    centers.push_back(far);
}

2-approximation for minimising the maximum distance to a center, and provably optimal (better than 2 is NP-hard).

When greedy is exactly optimal

If the feasible sets form a matroid, greedy by weight is optimal — no approximation involved. This covers:

• spanning trees → Kruskal;
• linearly independent vectors → linear basis;
• unit jobs with deadlines;
• partition and uniform matroids.

More generally, for matroid intersection (two matroids) an exact polynomial algorithm exists; for three, it is NP-hard. Recognising a matroid is the cleanest possible proof that greedy works — see Exchange Arguments.

Proving a ratio — the standard shapes

1. Charging. Assign each unit of ALG’s cost to something OPT must also pay for.
2. Lower-bounding OPT. Find a quantity $L\le \mathrm{OPT}$ with $\mathrm{ALG}\le \rho L$ (the MST bound for TSP, the matching bound for vertex cover).
3. Local optimality. At a local optimum, no improving move exists; sum those inequalities.
4. LP duality. Construct a feasible dual solution; weak duality bounds OPT.

See also: Approximation Algorithms · Exchange Arguments · Algorithmic Paradigms