Approximation Algorithms

Seven test suites, three runners

A team's continuous-integration pipeline runs seven test suites that take 6, 8, 4, 5, 2, 3 and 9 minutes. There are three identical runners, each runs one suite at a time, and a suite can't be split. The team wants every suite finished as early as possible: it wants to minimise the makespan, the time at which the last runner finishes.

In general there are $n$ jobs with sizes $p_1,\dots ,p_n$ and $m$ identical machines. A schedule assigns each job to one machine, a machine's load is the sum of its jobs' sizes, and the makespan is the largest load.

from itertools import product

J, m = [6, 8, 4, 5, 2, 3, 9], 3

def makespan(jobs, machine, m):
    loads = [0] * m
    for p, i in zip(jobs, machine):
        loads[i] += p
    return max(loads)

def best_makespan(jobs, m):
    """Try all m ** n schedules (small inputs only)."""
    return min(makespan(jobs, s, m) for s in product(range(m), repeat=len(jobs)))

assert sum(J) == 37 and 3 ** 7 == 2187
assert best_makespan(J, m) == 13

Why not just find the best schedule?

Trying every schedule is $m^n$ work: 2,187 schedules here, fine, but $3^{20}=3,486,784,401$ for twenty suites, and a real pipeline has hundreds. No shortcut is known. Minimum makespan is NP-hard already for two machines, and so are the other two problems in this module, minimum-weight vertex cover and the travelling salesman tour. This course takes NP-hardness as given, without the reductions: it means that no polynomial-time algorithm solves the problem exactly on every instance unless P = NP.

(Two refinements are worth knowing. For a fixed number of machines, a dynamic program over loads runs in time polynomial in $n$ and in the total size $\sum p_j$, which is pseudo-polynomial, as in module 09's knapsack. And the hardness is about the worst instance: many instances are easy.)

So this module gives up exactness, and keeps a proof.

The model: a factor on every instance

The ratio is a worst-case guarantee over all instances, not typical accuracy. A thousand instances where an algorithm is within 1% prove nothing, and one instance above $\alpha$ refutes the claim.

But how can we prove $\mathrm{A}\mathrm{L}\mathrm{G}\le \alpha ·\mathrm{O}\mathrm{P}\mathrm{T}$ when OPT is exactly the number we can't compute? Every proof in this module has the same shape. Find a quantity $L$ that we can reason about and that no solution can beat, so $L\le \mathrm{O}\mathrm{P}\mathrm{T}$, then prove $\mathrm{A}\mathrm{L}\mathrm{G}\le \alpha L$. For makespan, two lower bounds hold for every schedule. Some machine runs the largest job, and the busiest machine carries at least the average load:

$$\mathrm{O}\mathrm{P}\mathrm{T}\ge {max}_j{p}_j,\mathrm{O}\mathrm{P}\mathrm{T}\ge \frac{1}{m}\sum _j{p}_j.$$

For the seven suites that gives $max(9,\lceil 37/3\rceil )=13$ (loads are whole numbers, so we may round up), and the search above shows that 13 is achievable. On other instances the lower bound may be strictly below OPT; the proofs only need $L\le \mathrm{O}\mathrm{P}\mathrm{T}$.

Greedy on the seven suites

Greedy list scheduling takes the jobs in the order given and puts each one on a machine whose load is currently smallest (the lowest-numbered one on a tie). It never looks ahead, so it could even run while suites are still arriving.

The block below checks that the trace follows the rule. It doesn't schedule anything: it takes the runners the figure names and confirms that each one was least loaded at the time.

def follows_greedy(jobs, machine, m):
    loads = [0] * m
    for p, i in zip(jobs, machine):
        if loads[i] != min(loads) or loads.index(min(loads)) != i:
            return False
        loads[i] += p
    return True

greedy_J = [0, 1, 2, 2, 0, 0, 1]
assert follows_greedy(J, greedy_J, m) and makespan(J, greedy_J, m) == 17
assert 3 * 8 <= 37 - 9                      # the 9 started at load 8

Why greedy is within $2-1/m$

Proof. Let machine $i$ attain the makespan and let job $j$ be the last job placed on it, starting at load $s$, so $\mathrm{A}\mathrm{L}\mathrm{G}=s+p_j$. When $j$ was placed, machine $i$ was least loaded, so every machine had load at least $s$, and those loads consist of jobs other than $j$. Hence

$$ms\le \sum _k{p}_k-p_j.$$

Dividing by $m$ and adding $p_j$:

$$\mathrm{A}\mathrm{L}\mathrm{G}\le \frac{1}{m}\sum _k{p}_k+(1-\frac{1}{m})p_j.$$

The first term is at most OPT (the average-load bound) and $p_j\le \mathrm{O}\mathrm{P}\mathrm{T}$ (the largest-job bound), so $\mathrm{A}\mathrm{L}\mathrm{G}\le (2-1/m)\mathrm{O}\mathrm{P}\mathrm{T}$. $◻$

The step not to skip is leaving $p_j$ out of the average. Put it back in and the same argument only gives $2\mathrm{O}\mathrm{P}\mathrm{T}$. The $-1/m$ is real, because the bound is tight: for every $m$, some instance meets it exactly. Give greedy $m(m-1)$ jobs of size 1 and then one job of size $m$. The unit jobs spread evenly, load $m-1$ everywhere, and the big job lands on top: makespan $2m-1$. The optimum puts the big job alone and the unit jobs $m$ to a machine elsewhere: makespan $m$. The ratio is $(2m-1)/m=2-1/m$.

tight = [1] * 6 + [3]                       # m = 3: six unit jobs, then a 3
assert follows_greedy(tight, [0, 1, 2, 0, 1, 2, 0], m)
assert makespan(tight, [0, 1, 2, 0, 1, 2, 0], m) == 5
assert best_makespan(tight, m) == 3         # 5/3 = 2 - 1/3

Sort first: largest processing time

The tight instance hurts greedy because the big job comes last. LPT (largest processing time first) sorts the jobs by decreasing size, then runs greedy. On the seven suites it places 9, 8, 6, 5, 4, 3, 2 and ends with loads 12, 12 and 13: makespan 13, optimal here.

Sketch. Let $j$ be the last job on the busiest machine. Jobs placed after $j$ don't change the makespan and removing them can't raise OPT, so assume $j$ is placed last, which in LPT order makes it the smallest job. If $p_j\le \mathrm{O}\mathrm{P}\mathrm{T}/3$, the greedy argument gives

$$\mathrm{A}\mathrm{L}\mathrm{G}\le \mathrm{O}\mathrm{P}\mathrm{T}+p_j\le \frac{4}{3}\mathrm{O}\mathrm{P}\mathrm{T}.$$

Otherwise every job is larger than $\mathrm{O}\mathrm{P}\mathrm{T}/3$, so the optimum has at most two jobs per machine, and a case analysis shows LPT is optimal then. Skipped: that case analysis and the refinement to the exact $-1/(3m)$.

LPT is not optimal in general. On three machines, [5, 5, 4, 4, 3, 3, 3] is its tight case:

lpt_J = [2, 1, 1, 2, 2, 0, 0]               # runner of each suite of J, in J's order
order = sorted(range(7), key=lambda k: -J[k])
assert follows_greedy([J[k] for k in order], [lpt_J[k] for k in order], m)
assert makespan(J, lpt_J, m) == 13

trap = [5, 5, 4, 4, 3, 3, 3]
assert follows_greedy(trap, [0, 1, 2, 2, 0, 1, 0], m)
assert makespan(trap, [0, 1, 2, 2, 0, 1, 0], m) == 11
assert best_makespan(trap, m) == 9          # {5,4} {5,4} {3,3,3}: 11/9 = 4/3 - 1/9

For every fixed $\epsilon >0$ there is even a $(1+\epsilon )$-approximation whose running time is polynomial in $n$ (Hochbaum and Shmoys, 1987), cited here, not proved; its exponent grows as $\epsilon$ shrinks.

Vertex cover: round the linear program

A different problem. A graph $G=(V,E)$ has a weight $w_v>0$ on each vertex, and a vertex cover is a set $S$ of vertices that touches every edge. Find one of minimum total weight.

Write the problem as an integer program with a 0/1 variable $x_v$ for "$v$ is in the cover", then relax it (module 15) by allowing fractions:

$$\text{minimise}\sum _v{w}_v{x}_v$$

subject to $x_u+x_v\ge 1$ for every edge $uv$, and $0\le x_v\le 1$ for every vertex.

Every cover is a feasible point of this LP, so the LP's minimum is a lower bound: $\mathrm{L}\mathrm{P}\le \mathrm{O}\mathrm{P}\mathrm{T}$. And the LP can be solved in time polynomial in the input's bit length (module 15). The LP optimum is usually fractional. Here it is $x=(1,0,1,\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2})$, of value 12.5.

A classical fact, stated here without proof, makes that easy to check on small graphs: the vertex-cover LP always has an optimal solution with every $x_v\in \{0,\frac{1}{2},1\}$ (every corner of its polytope is of this form; Nemhauser and Trotter, 1974). So the block searches those points, written as $y=2x$:

from fractions import Fraction

H = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 6), (6, 3), (4, 6)]
w = [2, 4, 1, 4, 7, 5, 3]

def lp_half(n, edges, w):
    """(LP value, x) over x in {0, 1/2, 1}^n: exact, by the half-integrality fact."""
    best = min((sum(wi * yi for wi, yi in zip(w, y)), y)
               for y in product((0, 1, 2), repeat=n)
               if all(y[u] + y[v] >= 2 for u, v in edges))
    return Fraction(best[0], 2), [Fraction(yi, 2) for yi in best[1]]

def cheapest_cover(n, edges, w):
    covers = (S for S in product((0, 1), repeat=n) if all(S[u] or S[v] for u, v in edges))
    return min(sum(wi for wi, s in zip(w, S) if s) for S in covers)

lp, x = lp_half(7, H, w)
assert lp == Fraction(25, 2) and x == [1, 0, 1, Fraction(1, 2), Fraction(1, 2), Fraction(1, 2), Fraction(1, 2)]
assert cheapest_cover(7, H, w) == 13

Rounding. Keep every vertex with $x_v\ge \frac{1}{2}$.

Proof. Feasibility: every edge has $x_u+x_v\ge 1$, so one of its ends has $x\ge \frac{1}{2}$ and is kept. Cost: each kept vertex has $1\le 2x_v$, so $w_v\le 2w_v{x}_v$, and summing over the kept vertices gives at most $2{\sum }_v{w}_v{x}_v=2\mathrm{L}\mathrm{P}$. $◻$

keep = {v for v in range(7) if x[v] >= Fraction(1, 2)}
assert keep == {0, 2, 3, 4, 5, 6} and sum(w[v] for v in keep) == 22 <= 2 * lp

Rounding keeps weight 22 against the optimum's 13: a ratio of about 1.69, within 2. The lower bound here is 12.5, and every edge of the 4-cycle and chord gets exactly $\frac{1}{2}+\frac{1}{2}$.

No polynomial-time algorithm with ratio $2-\epsilon$, for a constant $\epsilon >0$, is known for vertex cover. Under the Unique Games Conjecture none exists (Khot and Regev, 2008); that is a conditional result, cited here.

Without weights: a matching is a lower bound

When every weight is 1, there is a cheaper route that needs no LP. Scan the edges in any order. Whenever an edge has neither end taken yet, take both ends.

Proof. Every edge is covered, since when it was scanned an end was already taken or both were taken then. The edges that triggered a "take both" share no vertex (their ends were untaken when they were chosen), so they form a matching $M$. Any cover needs a separate vertex for each edge of $M$, so $\mathrm{O}\mathrm{P}\mathrm{T}\ge |M|$, and the algorithm took $2|M|$. $◻$

The lower bound $L$ is now $|M|$, the size of the matching the scan built. On $H$, scanning in the listed order picks the edges 0–1, 2–3 and 4–5:

M = [(0, 1), (2, 3), (4, 5)]
ends = [v for e in M for v in e]
assert len(set(ends)) == 6                                   # a matching
assert all(u in ends or v in ends for u, v in H)             # nothing left to add: a cover
assert cheapest_cover(7, H, [1] * 7) == 4                     # 6 <= 2 * 4

The matching bound ignores weights, and with weights it fails: a cheap vertex matched to an expensive one drags the expensive one in. So the scan is a 2-approximation for the unweighted problem only; with weights, use LP rounding.

Metric travelling salesman: double a tree

The last problem: visit $n$ points and return to the start, as cheaply as possible. The distance $d$ must be a metric: $d(x,x)=0$, symmetric, and obeying the triangle inequality $d(x,z)\le d(x,y)+d(y,z)$. Here six points on a street grid use the Manhattan distance $|x_1-x_2|+|y_1-y_2|$, which is a metric.

Tree doubling. Build a minimum spanning tree $T$ (Prim's or Kruskal's algorithm, from a data-structures course). Walk around it depth first, which crosses every tree edge twice, and list each point the first time the walk reaches it (a preorder). Return to the start.

Proof. Delete one edge from an optimal tour: what is left is a path through every point, which is a spanning tree, so $w(T)\le \mathrm{O}\mathrm{P}\mathrm{T}$. The full walk around $T$ has length $2w(T)$. The preorder tour visits the points in the walk's order but jumps straight past points already seen. Each jump replaces a stretch of the walk by one direct hop, and by the triangle inequality (applied along the stretch) the hop is no longer than the stretch. $◻$

from itertools import combinations, permutations

P = [(2, 5), (3, 8), (8, 8), (5, 3), (9, 3), (3, 6)]
d = lambda a, b: abs(P[a][0] - P[b][0]) + abs(P[a][1] - P[b][1])
length = lambda t: sum(d(t[k], t[(k + 1) % len(t)]) for k in range(len(t)))

def connected(edges, n):
    seen, todo = {0}, [0]
    while todo:
        a = todo.pop()
        for b in {v for e in edges if a in e for v in e} - seen:
            seen.add(b)
            todo.append(b)
    return len(seen) == n

# A stand-in for Prim's algorithm: the lightest of all 3,003 sets of 5 edges that connect the points.
mst_weight = min(sum(d(a, b) for a, b in T)
                 for T in combinations(combinations(range(6), 2), 5) if connected(T, 6))
T = [(0, 5), (5, 1), (1, 2), (0, 3), (3, 4)]
tour = [0, 3, 4, 5, 1, 2]                    # preorder from 0, children in increasing order
assert sum(d(a, b) for a, b in T) == mst_weight == 18
assert length(tour) == 34 <= 2 * mst_weight
assert min(length((0,) + p) for p in permutations(range(1, 6))) == 24     # the optimum

The tour 0, 3, 4, 5, 1, 2 has length 34, within the promised 36; the best tour has length 24 (ratio about 1.42). Christofides' algorithm (1976) adds a minimum-weight perfect matching on the tree's odd-degree vertices instead of doubling every edge and reaches $3/2$; a 2021 randomized algorithm (Karlin, Klein and Oveis Gharan) improves $3/2$, in expectation, by a constant above ${10}^{-36}$. Both are cited, not proved.

The triangle inequality is not a technicality. Without it, for any constant $\alpha$, no polynomial-time $\alpha$-approximation exists for the travelling salesman problem unless P = NP (Sahni and Gonzalez, 1976).

Complexity

All times are worst case in the word-RAM model, with sizes, weights and coordinates that fit in a machine word; $n$ is the number of jobs, vertices or points.

Exact search costs $m^n$ schedules, $2^n$ vertex sets or $(n-1)!/2$ tours. The ratios are proved; the tight instances show that greedy's and LPT's can't be improved.

Measure the claim

On random small instances generated with seed 451 (200 job lists with $m\in \{2,3\}$, at most 7 jobs of size 1 to 20; 200 graphs of at most 8 vertices with weights 1 to 9; 100 sets of at most 7 points on a $10\times 10$ grid), the worst ratios observed against exact brute force were:

These are measurements on these instances, not theorems. Random instances rarely find the worst case: greedy never came near $5/3$, and LPT not near $11/9$, although the tight instances above meet both bounds exactly. The two cover algorithms did reach 2, on tiny graphs. The matching scan takes both ends of a single edge, where one end suffices. Rounding reached 2 on a triangle with weights 3, 6 and 3, where the LP has several optimal solutions and the search returned $x=\frac{1}{2}$ everywhere (value 6): rounding keeps all three vertices, weight 12, while the cover $\{0,2\}$ costs 6. Worst cases are built, not sampled.

A problem that looks different

A courier firm packs parcels of sizes between 0 and 1 into vans of capacity 1, and wants to use as few vans as possible. Nobody can compute the minimum for a day's thousands of parcels. What number is surely below the minimum, and what simple packing rule could you charge to it? It is not solved here, and it is not the lab's last problem.

Practise

In the lab you schedule jobs greedily while the drawing shows why the last job can't start too late; predict and then watch the cover that an edge scan builds on a new graph, next to the LP's rounding; write tree doubling and test it against brute force; build instances on which LPT meets its bound exactly and measure how far random instances stay from it; and solve a placement problem that doesn't say what it is.

Recap

You can now: say what an $\alpha$-approximation guarantees; prove greedy list scheduling $(2-1/m)$-approximate and build its tight instance; round the vertex-cover LP and prove the factor 2; prove the maximal-matching cover and tree doubling 2-approximate, naming the lower bound each one uses.

Invariant: every proof charges the algorithm to a lower bound: $\mathrm{A}\mathrm{L}\mathrm{G}\le \alpha L$ and $L\le \mathrm{O}\mathrm{P}\mathrm{T}$, with $L$ the largest job and the average load, the LP value, the size of a matching, or the weight of a minimum spanning tree.

Complexity achieved: polynomial time (at most $O(n^2)$ here, plus solving one LP) within factor $2-1/m$, $4/3-1/(3m)$ or 2 of the optimum on every instance, against $m^n$, $2^n$ and $(n-1)!/2$ for exact search.

Failure mode: trusting a ratio measured on random instances. Worst cases are constructed, and the tight families meet the bound exactly.

In real software: NetworkX's approximation package has min_weighted_vertex_cover, a 2-approximation for weighted vertex cover by the local-ratio method, and christofides for metric tours; see the module notes for versions.

Retrieval (module 17): on a bipartite graph, does rounding the vertex-cover LP ever lose anything? What does total unimodularity say about the LP's corners there?

Check yourself

1. Why is greedy list scheduling within $2-1/m$ of optimal, and where does the $-1/m$ come from?
2. Round the vertex-cover LP at 0.6, or drop the triangle inequality from the tour problem. What breaks in each proof?
3. On $H$, compare LP rounding, the matching cover and the optimum. Which lower bound does each proof charge to, and which algorithm would you use with weights?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.