How to Build an Approximation Proof

Start with the inequality you need

An approximation algorithm must return a feasible solution, run in polynomial time, and meet a guarantee on every instance. The guarantee tells us which way the proof must go. Write for the value of the algorithm’s solution and for the value of an optimal solution:

Here and . For minimisation, we need to show that the algorithm has not paid much more than some lower bound on the optimum: . For maximisation, we need to show that the algorithm has earned almost as much as some upper bound : .

This is why it helps to name the optimum before trying to analyse a greedy choice. We do not know its solution, but we can ask what every feasible solution must pay, or what any feasible solution could possibly earn.

Find something both sides can count

The algorithm’s objective and the optimum may be hard to compare directly. Look instead for a count or score that relates to both. It may be a set of witnesses, the size of the input, a degree sum, or the number of edges. Such a quantity is a bridge, not necessarily the objective itself.

In bounded-frequency Set Cover, the algorithm chooses uncovered elements and selects all sets containing each chosen element. If every element occurs in at most input sets, it selects at most sets per witness:

Why does say anything about the optimum? Once a witness is chosen, every input set containing is selected, and all of its elements become covered. A later witness cannot belong to any of those sets. Thus no input set contains two witnesses. Every cover needs at least one set per witness:

The property of that matters is not merely that the algorithm chose it. It is that one input set cannot account for two of its elements. That gives a lower bound on what an optimal cover must pay.

Let the assumption tell you what to count

A similar-looking Set Cover problem can need a different bridge. Suppose every input set contains at most elements. Choosing one set containing an uncovered element at a time takes at most iterations, so . Any cover of needs at least sets: sets can cover at most elements, even before accounting for overlap. Hence

These two algorithms share a factor , but not a proof. Frequency bounds what the algorithm selects per witness; set size bounds what the optimum can cover per selected set. Before reusing an argument, ask exactly which side of the comparison the input restriction controls.

When the bridge overcounts, measure the error

For Maximum Coverage on a graph, choose up to vertices of highest degree; call their set . The degree sum

is convenient because sorting makes at least as large as the degree sum of any set of at most vertices. In particular, if is an optimal choice, then

But is not the algorithm’s value. An edge with both endpoints in contributes twice to and only once to the covered-edge count . If is the set of these internal edges, then

There are at most internal edges in a simple graph. The hypothesis that the maximum degree matters because : it makes the error smaller than an -fraction of the bridge,

Now the comparison reaches the actual objective:

This is a useful question for a greedy algorithm: What does its choice rule maximise that is easier to analyse than its actual score? Then ask what that surrogate counts incorrectly, and whether the mistake is small enough to pay for.

Sometimes local optimality is the bridge

Not every proof uses a chosen witness or a sorted score. For Maximum Cut, move a vertex across the cut whenever doing so increases its size. At termination, each vertex has at least as many neighbours across the cut as on its own side: otherwise moving would improve the cut.

Let and count those two kinds of neighbours. The condition holds for each vertex. Summing it counts each cut edge twice and each same-side edge twice:

So . No cut can contain more than all edges, giving and therefore . The algorithm’s stopping condition became a relation between two counts; the crude upper bound completed the comparison.

A working checklist

When facing a new approximation problem, try these questions in order:

1. What is the objective? Name the returned value , the optimum , and the direction of the desired inequality. Check feasibility separately.
2. What does one algorithmic choice guarantee? Record what it selects, removes, covers, or forbids. This often supplies a witness or a local inequality.
3. What can every optimal solution do? Bound how many witnesses one optimal choice can handle, or how large any feasible value can be. For minimisation seek a lower bound; for maximisation seek an upper bound.
4. Is the convenient count the actual objective? If not, write an equality that exposes the overlap, double counting, or loss. Bound that error before substituting the optimum.
5. Do the inequalities join in the right direction? Write the chain from to one step at a time, explaining what licenses each step. If the chain cannot be joined, the proposed bridge is not enough.
6. Does the algorithm finish efficiently? Bound the number of choices and the work per choice; a good ratio alone does not establish a polynomial-time approximation algorithm.

The central habit is to separate what the algorithm produces from what is easy to count. Find a quantity that speaks to both the algorithm and the unknown optimum, then account explicitly for any gap between that quantity and the objective.