Approximation Algorithms

Many important problems are NP-complete, so nobody knows a fast exact algorithm. This lesson shows the alternative: fast algorithms that are guaranteed to return an answer within a known factor of the best possible one. You will run approxVertexCover, approxTspTour, greedySetCover, randomized max-3SAT, approxMinWeightVc (linear-programming rounding), mergeLists, exactSubsetSum, trim and approxSubsetSum step by step, and every run also computes the brute-force optimum so you can see the real ratio against the promised one, with a ratio bar chart and a proof-chain table under every procedure.

What an approximation ratio means

An optimization problem asks for the best answer among many valid ones: the shortest tour, the fewest guards, the largest total that still fits. Many important optimization problems are NP-hard (see C34 · NP-completeness): nobody knows an algorithm that is guaranteed to find the best answer in polynomial time (time that grows like n², n³, … rather than 2ⁿ), and finding one would settle the biggest open question in computer science. This lesson shows the practical escape hatch: a fast algorithm that is not always perfect but comes with a proof of how far from perfect it can be.

Imagine a delivery driver who cannot afford to test every possible route. A dispatcher promises: "the route you pick will never be more than twice as long as the very shortest one." The dispatcher does not know the shortest route either, yet the promise is provable. That promise is an approximation ratio.

For an optimization problem, let C* be the cost of an optimal solution and C the cost of the solution our algorithm returns. The algorithm is a ρ(n)-approximation if for every input of size n, max(C/C*, C*/C) ≤ ρ(n). For a minimization problem this is C ≤ ρ·C*; for a maximization problem it is C* ≤ ρ·C. The ratio is always ≥ 1, and 1 means "exactly optimal".

Small example. A minimization algorithm returns a cover of 6 guards while the true minimum is 4: ratio 6/4 = 1.5. A maximization algorithm satisfies 7 of 8 rules while the best possible is 8: ratio 8/7 ≈ 1.14. Both numbers are "how many times worse than perfect", and both are at least 1.

Two stronger notions appear at the end of this lesson. An approximation scheme takes an extra input ε > 0 (a small number such as 0.1, "I accept an answer 10% off") and is a (1+ε)-approximation for any fixed ε. It is a PTAS if it runs in polynomial time for each fixed ε, and a FPTAS if the time is polynomial in both the input size and 1/ε. approxSubsetSum below is an FPTAS.

How to read the animations: each one runs the pseudocode printed beside it, one row per line, and finishes with a brute-force optimum (try every candidate answer; feasible only because the inputs are tiny) and the measured ratio. Below every procedure a ratio bar chart compares the measured ratio of several inputs with the proven bound, and a proof-chain table shows the inequalities of the proof with real numbers.

Pitfall. The ratio compares against the optimum, which you normally cannot compute. A measured ratio on a few friendly inputs proves nothing; only the proof does. The demos here can print the true ratio only because brute force is affordable on 5-to-9 item inputs.

Under the hood. Every proof in this lesson needs a computable lower bound L on the unknown C* (for a minimization problem): a value you can calculate quickly that C* can never go below. Then "algorithm cost ≤ ρ·L ≤ ρ·C*" finishes the argument without ever computing C*. The lower bounds used here are a matching (vertex cover), a spanning tree (TSP), the greedy charging argument (set cover), a linear program (weighted vertex cover) and a trimming invariant (subset sum).

Approximation ratio ρ ≥ 1 = worst-case (algorithm cost ÷ optimum) for minimization, (optimum ÷ algorithm cost) for maximization. A proof needs an easy lower bound on the optimum; the ratio is then a fixed multiple of that bound.

Maths → code. The approximation ratio of a solution of cost C against the optimum C* is max(C/C*, C*/C): the first quotient for minimization, the second for maximization, always ≥ 1, and exactly 1 only for an optimal answer.

Input size → what's feasible. Computing the exact C* needs brute force (n ≤ 25 for subset problems, n ≤ 10 for tours), so measured ratios on this page use tiny inputs; the provable ratios below hold for every input size.

approxVertexCover

A graph is dots (vertices) joined by lines (edges); see C22 · graph basics. A vertex cover of an undirected graph is a set of vertices such that every edge has at least one endpoint in the set. Finding a smallest one is NP-hard. The procedure below repeatedly takes an arbitrary remaining edge (u, v), adds both endpoints, and deletes every edge touching u or v. (This page always takes the first remaining edge in list order.)

You must place security guards on street corners so that every street has a guard at one of its two ends, using as few guards as possible. The cheap trick: pick any street nobody watches yet, put guards at both ends, and forget every street those two guards now watch. Repeat until every street is watched.

Small example. A path a–b–c–d has edges ab, bc, cd. Pick ab: guards at a and b, which also watch bc. Pick cd: guards at c and d. The algorithm hires 4 guards, but guards at b and c alone would already watch all three streets, so the optimum is 2 and the ratio is exactly 2.

Reading the pseudocode. Line 1 starts with no guards. Line 2 copies the edge set into E′, the "still unwatched" streets. Lines 3–6 are the loop: pick any unwatched edge (line 4), hire both its endpoints (line 5), discard every street they watch (line 6). Line 7 returns the guards. Every loop round permanently removes at least the picked edge, so the loop ends after at most E rounds.

Ratio bar chart and proof chain (all numbers computed live on this page by the same procedure plus a brute-force optimum):

Dart implementation (vertices 0..n−1, edges as [u, v] pairs). Index shift: the pseudocode is already index-free (it works with vertices and edge sets, not array positions), so nothing needs shifting from pseudocode to Dart; only the set E′ becomes the list rest, refilled each round.

Maths → code. The 2-approximation argument says |C| = 2|A| ≤ 2|C*|, where A is the set of edges picked on line 4. The code below rebuilds A, checks that it is a matching (no shared endpoint), that |C| = 2|A|, that any cover needs at least |A| vertices, and so |C| ≤ 2|C*|.

Input size → what's feasible. V + E ≤ 10⁴ → the list-filtering Dart version above (O(E) per round, O(E²) worst case) is instant; E ≈ 10⁶ → mark vertices in a boolean array and make one pass over the edges for Θ(V + E). Computing the exact optimum by trying all 2ⁿ subsets stops at n ≈ 25.

Pitfall: "just take the highest-degree vertex" is NOT a 2-approximation. That natural-sounding greedy can be Θ(log n) times worse than optimal on adversarial graphs (see the question bank). The matching-based procedure looks wasteful because it adds two vertices per edge, but that waste is exactly what makes the proof work.
Running time. With adjacency lists and a marker per vertex it is O(V + E): each edge is examined once when chosen or removed. The Dart version above re-filters the list each round (O(E) per round, O(E·V) worst case) to keep the code obvious.

Why it is a 2-approximation. The edges picked on line 4 form a set A in which no two edges share an endpoint (a matching), because line 6 removes every edge touching a chosen vertex. Any cover, including an optimal one, must contain at least one endpoint of each edge of A, and those endpoints are all different, so |C*| ≥ |A|. The algorithm adds exactly two vertices per edge of A, so |C| = 2|A| ≤ 2|C*|. The star in Example 2 shows the factor 2 can really happen. Correctness (it is a cover): the loop only stops when E′ is empty, and every edge left E′ only because one of its endpoints entered C.

approxVertexCover: pick an uncovered edge, take both ends. Cover size = 2 × (matching size) ≤ 2 × OPT, because any cover needs one vertex per matched edge. Ratio 2, time O(V + E).

approxTspTour

The traveling-salesman problem (TSP) asks for the cheapest Hamiltonian cycle (a round trip visiting every vertex exactly once) in a complete graph (every pair of towns has a road) with edge costs c. The cost function satisfies the triangle inequality if c(u, w) ≤ c(u, v) + c(v, w) for all u, v, w: going directly is never worse than going via a third town. Straight-line (Euclidean) distances always satisfy it, and the animations below use Euclidean points. A minimum spanning tree (MST) is the cheapest set of edges connecting all vertices with no cycle; the procedure calls primMst from C23 · minimum spanning trees, which is why Prim's steps appear inside the animation. A preorder tree walk lists a vertex when first reached, then walks each child subtree in turn.

A courier must visit every town once and come home. First lay the cheapest set of roads that connects all towns (a minimum spanning tree). Then walk around that tree like tracing a fence, but whenever the fence walk would revisit a town, cut straight across to the next new one. Cutting across is never longer, provided the map obeys the triangle inequality.

Small example. Four towns on a straight road at positions 0, 2, 5, 9. The MST is the road itself (weight 9). The preorder walk visits a, b, c, d and returns from d to a: total 2 + 3 + 4 + 9 = 18, and no tour can beat 18, so here the tour is optimal.

Reading the pseudocode. Line 1 chooses the starting vertex (the root). Line 2 grows the MST from the root with Prim (each step adds the cheapest edge leaving the tree; the green edges in the animation). Line 3 lists the vertices in preorder; the animation shows the detour a full walk would take and the shortcut H takes instead. Line 4 returns that list as a cycle (closing the last vertex back to r).

Dart implementation. Index shift: the pseudocode names vertices a, b, c, … (vertex a is index 0) and starts Prim from the root; the Dart code fixes the root to vertex 0 (any root works) and keeps Prim's state in 0-based arrays parent, key, inTree.

Maths → code. Line 2 is primMst from root 0. This is the array version of Prim's algorithm (extract-min by linear scan) with an independent Kruskal check of the tree weight.

Maths → code. Lines 3–4: the tour H is the preorder of the tree. A full walk W of the tree (every edge down and back up) revisits vertices; keeping only the first visit of each vertex (the shortcut) gives exactly the preorder, which is the tour the procedure returns.

Maths → code. The 2-approximation proof as three inequalities, c(T) ≤ c(H*), c(W) = 2c(T) and c(H) ≤ c(W) (triangle inequality), combined into c(H) ≤ 2c(H*).

Maths → code. General TSP: without the triangle inequality no constant ratio ρ is possible unless P = NP. The reduction gives edges of G cost 1 and non-edges cost ρ|V| + 1; a ρ-approximation then answers Hamiltonian cycle, which the code checks against brute force.

Input size → what's feasible. n ≤ 3000 cities → the Θ(V²) Prim here is about 10⁷ distance evaluations (fine); n = 10⁵ → build the MST from a geometric structure (Delaunay, O(n log n)) instead; the exact optimum needs n ≤ 10 by brute force ((n−1)! tours) or n ≤ 20 with Held–Karp.

Pitfall. The guarantee needs the triangle inequality. Without it, no constant ratio is possible unless P = NP (the general-TSP hardness result), and the MST-preorder tour can be arbitrarily bad. Also, the preorder tour is not a walk along tree edges; every shortcut is a direct edge that may not be in the tree.
Running time. Θ(V²) with the array-based primMst used here (the graph is complete, so E = Θ(V²)); the preorder walk is Θ(V). The optimum in each animation is found by trying all (n−1)! tours, which is only sensible for n ≤ 8.

Why it is a 2-approximation. (1) Delete one edge from an optimal tour H* and you get a spanning tree, so c(T) ≤ c(H*). (2) A full walk W of T traverses every tree edge twice, so c(W) = 2c(T) ≤ 2c(H*). (3) The tour H from line 3 is W with repeated vertices skipped; by the triangle inequality each skip does not increase the cost, so c(H) ≤ c(W) ≤ 2c(H*). The proof-chain table above prints these three inequalities with numbers for each example.

approxTspTour: MST (a lower bound, since a tour minus one edge is a spanning tree) → preorder walk → shortcut repeats. Triangle inequality makes shortcuts free, so cost ≤ 2·MST ≤ 2·OPT.

greedySetCover

An instance of set cover is a finite set X and a family F of subsets of X whose union is X. A cover is a subfamily C ⊆ F whose union is X, and we want the fewest sets. Greedy (see C16 · greedy algorithms) means "take the locally best-looking choice now and never undo it". The procedure keeps U, the uncovered elements, and each round picks the set covering the most elements of U (ties go to the lowest-numbered set on this page; any tie-break is allowed).

You are forming a committee that must contain at least one person with every needed skill. Each candidate has some skills. Greedy rule: at every step hire the person who adds the most skills still missing, until nothing is missing.

Small example. X = {1,…,6}, S1 = {1,2,3,4}, S2 = {1,2,5}, S3 = {3,4,6}. Greedy takes S1 (4 new elements), then S2 (covers 5), then S3 (covers 6): 3 sets. But S2 ∪ S3 already covers everything with 2 sets. Greedy was tempted by the big set S1 and paid for it: ratio 3/2.

Reading the pseudocode. Lines 1–2 start with everything uncovered and nothing chosen. Line 3 loops while something is uncovered. Line 4 is the greedy decision: pick the set with the largest |S ∩ U|. Lines 5–6 mark its elements covered and record it. The animation prints every set's gain so the maximum is visible.

Dart implementation. Index shift: elements are numbered 1..m (kept 1-based on purpose: they are values, not positions), while the family f is a 0-based list, so the set labelled S_k in the animation is f[k-1] and the function returns 0-based set indices.

Maths → code. The harmonic bound: each element pays 1 / (number of new elements covered by the set that first covers it); the prices add up to |C|, every set of an optimal cover pays at most H(|S|) ≤ H(d), and H(d) ≤ ln d + 1. The code computes the prices and checks each step.

Input size → what's feasible. |X|, |F| ≤ 10³ → the plain Dart loop (O(|X|·|F|) per round) is fine; Σ|S| ≈ 10⁶ → use bucket queues for O(Σ|S|); the exact optimum needs |F| ≤ 25 (2^|F| subsets).

Pitfall. H(d) grows with the largest set size d, and the bound is a worst-case guarantee, not a prediction: on most inputs greedy is optimal or off by one set. Also, the tie-break matters for which cover you get (not for the bound).
Running time. Naively O(|X|·|F|·min(|X|, |F|)); with counters and buckets it is O(Σ|S|), linear in the input size.

Ratio H(d). Charge each newly covered element 1/(number of elements the chosen set newly covered). The total charge is |C|. Any set S of the optimal cover is charged at most H(|S|) = 1 + 1/2 + … + 1/|S| in total (its uncovered part shrinks while greedy always has a set at least as good available), so |C| ≤ Σ over optimal sets of H(|S|) ≤ |C*| · H(d) where d is the largest set size. Hence a (ln |X| + 1)-approximation, because H(d) ≤ ln d + 1. Example 2 is a small instance where greedy really is worse than optimal.

greedySetCover: always take the set with the most uncovered elements. Ratio H(d) = 1 + 1/2 + … + 1/d ≤ ln|X| + 1, and up to constants nothing polynomial can do better unless P = NP.

Randomized max-3SAT

A literal is a variable x or its negation ¬x. A clause is an OR of literals (true when at least one literal is true), and a 3-CNF formula is an AND of clauses, each with exactly three literals on three different variables. max-3SAT asks for the truth assignment that makes as many clauses true as possible. A randomized algorithm may flip coins; its guarantee is about the expected value (the average over all coin outcomes; see C05 · probabilistic analysis for indicator variables and linearity of expectation).

A quiz has m three-answer clauses, each of the form "at least one of these three statements must be true". You cannot find the perfect answer sheet, so you just flip a fair coin for every variable. Because a clause with three different variables fails only when all three coins land the "wrong" way, each clause is satisfied with probability 7/8.

Small example. Take the single clause (x1 ∨ ¬x2 ∨ x3). It is false only for x1 = 0, x2 = 1, x3 = 0: exactly 1 of the 2³ = 8 equally likely assignments. So it is satisfied with probability 7/8, and with m such clauses we expect 7m/8 of them to be satisfied.

The algorithm sets every variable to 1 independently with probability 1/2. The three rows below spell that out; the random bits come from a seeded generator so runs repeat exactly.

Reading the pseudocode. Rows 1–2 set each variable by a fair coin, independently; row 3 returns the assignment. The animation then scores each clause: green means at least one literal is 1, red means all three are 0. The last frame compares the single run, the average over 300 other runs, and the brute-force optimum.

Dart implementation. Index shift: variables are numbered 1..n in formulas and in literals (¬x2 is written −2); the code reads literal l as variable x[l.abs() - 1], converting to 0-based storage, and l > 0 means "positive literal".

Maths → code. Clause probability: a clause fails only when all three literals are 0, probability 1/8, so each clause is satisfied with probability 7/8 and E[Y] = 7m/8; the optimum is at most m, so the expected ratio is at most 8/7. The code averages over all 2ⁿ assignments for the exact value, then compares a seeded simulation.

Input size → what's feasible. m up to 10⁷ clauses → drawing and scoring is Θ(n + m), trivially fast; exact enumeration of all assignments (used only to check the 7m/8 identity) is for n ≤ 20.

Pitfall. The 7/8 needs the three literals of a clause to be on three different variables. A clause like (x1 ∨ x1 ∨ x2) or (x1 ∨ ¬x1 ∨ x2) breaks the arithmetic (the first is satisfied with probability 3/4, the second always). Also, a single run can land below 7m/8; only the average is guaranteed. The custom input rejects repeated variables for this reason.

Expected ratio 8/7. Let Y_i = 1 if clause i is satisfied. Its literals are on three different variables, so Pr[clause i unsatisfied] = (1/2)³ = 1/8 and E[Y_i] = 7/8. By linearity of expectation E[satisfied] = 7m/8, and since the optimum is at most m, the expected ratio is at most m / (7m/8) = 8/7. Linearity needs no independence between clauses, which is why clauses sharing variables are fine. A single run may do worse or better; only the average over the coin flips is guaranteed. It also proves that some assignment satisfies at least 7m/8 clauses (an average cannot exceed its maximum).

Random assignment: each clause true with probability 7/8, so E[satisfied] = 7m/8 ≥ (7/8)·OPT. Expected ratio ≤ 8/7, in Θ(n + m) time, with no cleverness at all.

approxMinWeightVc (LP rounding)

In minimum-weight vertex cover each vertex v has a weight w(v) (its price), and we minimize the total weight of the cover. Write it as a 0/1 integer program (x(v) = 1 means v is in the cover, 0 means not): minimize Σ w(v)x(v) subject to x(u) + x(v) ≥ 1 for every edge (u, v). The LP relaxation (linear program, see C29 · linear programming) allows any 0 ≤ x(v) ≤ 1, which makes the problem solvable in polynomial time. Its optimum is a lower bound on the integer optimum, because every real cover is also a feasible fractional solution.

Suppose each guard has a different salary. A fractional guard may be hired "half-time". Solve that easier fractional problem exactly, then round every guard who is at least half-hired up to full-time and everyone else down to zero. Rounding at most doubles each salary.

Small example. A triangle a–b–c with all weights 1. Fractional solution: x = ½ everywhere (every edge gets ½ + ½ = 1), cost 3/2. Rounding turns all three up to 1: cover weight 3. The best real cover uses 2 vertices, so the ratio is 3/2 ≤ 2, and 3 ≤ 2 × (3/2), exactly the proof's inequality.

Line 2 of the procedure solves the LP; a real implementation uses a general LP solver. For the tiny graphs here, the page computes the LP optimum by enumerating every assignment of x(v) ∈ {0, ½, 1}, which is enough because the basic optimal solutions of this particular LP are half-integral (every coordinate is 0, ½ or 1).

Reading the pseudocode. Line 1 starts empty; line 2 gets the fractional optimum x̄; lines 3–5 visit every vertex and add it when x̄(v) ≥ ½; line 6 returns. The animation shows each vertex's weight w and its fractional value x̄ so you can see why some vertices are rounded down.

Dart implementation. Index shift: vertices are 0..n−1. The LP solution is stored in halves (0, 1, 2 mean x̄ = 0, ½, 1) so all arithmetic stays in integers; hence the test x[v] >= 1 means x̄(v) ≥ ½.

Maths → code. The rounding bound: rounding every x̄(v) ≥ ½ up gives w(C) ≤ 2·LP* and LP* ≤ OPT. The code checks the LP constraint, that each edge keeps an endpoint, the weight inequality, and shows the integrality gap on K_n (LP* = n/2 versus OPT = n − 1, ratio → 2).

Input size → what's feasible. n ≤ 14 → the {0, ½, 1}ⁿ enumeration used on this page (3ⁿ candidates) is enough to teach the idea; real graphs with n ≈ 10⁵ → solve the LP with a solver (or by the bipartite-matching reduction), still polynomial.

Pitfall. Rounding must go up at exactly ½ (≥, not >): with x̄(u) = x̄(v) = ½ on an edge, rounding both down would leave the edge uncovered. Also do not confuse the LP optimum (a lower bound, possibly fractional) with the cover weight the algorithm returns.
Running time. One LP solve (polynomial) plus Θ(V) for rounding; the page's 3ⁿ enumeration is only a stand-in for a real LP solver on tiny graphs.

Why it is a 2-approximation. The rounded set C is a cover: for each edge, x̄(u) + x̄(v) ≥ 1, so at least one endpoint has x̄ ≥ ½ and is picked. Its weight is Σ over v in C of w(v) ≤ Σ w(v)·2x̄(v) = 2·(LP optimum) ≤ 2·(integer optimum). The odd cycle (triangle with unit weights) has LP value 3/2 with every x̄ = ½, so the rounded cover has weight 3 against an optimum of 2.

LP rounding: solve the fractional version (a lower bound), round x̄ ≥ ½ up to 1 and the rest down to 0. Every vertex costs at most twice its fractional share, so weight ≤ 2·LP ≤ 2·OPT.

mergeLists

The subset-sum procedures below repeatedly combine two sorted lists into one. mergeLists(a, b) returns the sorted list that is the merge of its two sorted input lists with duplicate values removed. It works like the MERGE step of merge sort (C02), and runs in time O(|a| + |b|).

Two queues of people sorted by height are merged into one sorted queue by comparing the two front people and letting the shorter one go first. If both fronts are equally tall, they are the same person twice, so only one goes through.

Small example. a = ⟨0, 130⟩ and b = ⟨134, 264⟩. Compare 0 and 134: 0 goes. Compare 130 and 134: 130 goes. a is used up, so the rest of b (134, 264) is appended: ⟨0, 130, 134, 264⟩, the list for S = ⟨130, 134, …⟩ in the example below.

Reading the pseudocode. Two pointers i and j mark the next unused element of each list (the pink markers). Each loop round compares the two pointed-to values and moves exactly one value into the output out (or one shared value, advancing both pointers). When one list runs out, the other's remainder is already sorted and is appended in one go (line 10).

Dart implementation. Index note: the pointers i, j start at 0 in the pseudocode and in Dart, and the loop test "i < |a|" is i < a.length.

Maths → code. Pointers are positions counted from 0: the next unused element of a is a[i], so the loop runs while i < a.length and j < b.length, and a finished list is exactly one whose pointer equals its length.

Maths → code. Each loop pass advances at least one pointer, so mergeLists takes at most |a| + |b| passes and produces at most |a| + |b| values: Θ(|a| + |b|).

Input size → what's feasible. |a| + |b| ≤ 10⁷ → two pointers is instant (10⁷ steps ≈ 0.1 s); re-sorting would cost an extra log factor and ignore the sortedness.

Pitfall. Merging equal values must advance both pointers; advancing only one leaves a duplicate in the output, and duplicates would let the lists in exactSubsetSum double for no reason. Both inputs must already be sorted, or the output is not.

Running time. Every loop round moves at least one element to the output and the output has at most |a| + |b| elements, so the loop runs at most |a| + |b| times, each with one comparison: Θ(|a| + |b|). The proof table above counts the real comparisons for each example against the bound |a| + |b| − 1 for the loop.

mergeLists = merge step of merge sort plus "equal values count once". Linear in the total length, output stays sorted and duplicate-free.

exactSubsetSum

In the subset-sum problem we are given a set S of positive integers and a target t, and want the subset with the largest sum not exceeding t. Let P_i be the set of all sums of subsets of the first i numbers; then P_i = P_i−1 ∪ (P_i−1 + x_i) (each old sum either skips x_i or uses it), where L + x means "add x to every element of L".

You have coins of different values and want a handful summing to as close as possible to a price tag without going over. Keep a sorted list of every total you can already make; each new coin makes a shifted copy of that list; merge the two and throw away totals above the price.

Small example. S = ⟨1, 4, 5⟩, t = 6. L₀ = ⟨0⟩. After coin 1: ⟨0, 1⟩. After coin 4: merge ⟨0, 1⟩ with ⟨4, 5⟩ = ⟨0, 1, 4, 5⟩. After coin 5: merge with ⟨5, 6, 9, 10⟩, drop sums above 6: ⟨0, 1, 4, 5, 6⟩. The largest is 6 = 1 + 5.

Reading the pseudocode. Line 1 starts the list with the empty sum 0. Lines 2–5 are the loop over the numbers: line 3 builds the shifted copy, line 4 merges it in (via mergeLists) and line 5 drops sums above t (they can never come back down because all numbers are positive). Line 6 returns the largest survivor.

Dart implementation. Index shift: the pseudocode's s[i] becomes the loop variable of for (final x in s), so no index arithmetic remains; the successive lists are one variable l that is overwritten each round; "the largest value in L" is l.last because the list is sorted.

Maths → code. Each round can at most double the list: |L_i| ≤ 2ⁱ. For the numbers 1, 2, 4, …, 512 every subset sum is different, so the lists really do reach 2ⁱ (until the target t cuts them off).

Input size → what's feasible. n ≤ 25 or t ≤ 10⁶ → exact lists stay small enough (2²⁵ ≈ 3·10⁷); n = 100 with large numbers → use the trimmed version below.

Pitfall. "Exact" is not "fast". |L_i| can reach 2ⁱ, so exactSubsetSum is exponential: O(2ⁿ) in the worst case. It is only fast when the target t is small (then |L_i| ≤ t+1, giving pseudo-polynomial time). The custom player is limited to 6 numbers so the lists stay readable.

Correctness. By induction on i, L_i is a sorted list of every element of P_i that is ≤ t. The base case P₀ = {0} is line 1; the step is identity P_i = P_i−1 ∪ (P_i−1 + x_i), and removing sums above t is safe because all numbers are positive. The table above shows the list sizes doubling on a "worst-case" instance (1, 2, 4, 8, …) and staying tiny when t is small.

exactSubsetSum: keep every reachable sum ≤ t; each coin merges the list with a shifted copy. Exact, but the list can double every round, O(2ⁿ).

trim

Trimming is the idea that makes the exact procedure fast. We use a trimming parameter δ with 0 < δ < 1. To trim a sorted list L by δ means to remove as many elements as possible so that every removed y still has a stand-in z remaining in the list with y/(1+δ) ≤ z ≤ y.

Two prices of 101 and 102 are nearly the same. To keep a shopping list short, you keep one of them and let it stand in for the other. trim keeps a value only if it is more than a factor (1+δ) bigger than the last value kept.

Small example. δ = 0.1 and L = ⟨10, 11, 12, 15⟩. Keep 10. Is 11 > 10 × 1.1 = 11? No (equal), so 10 stands in for 11. Is 12 > 11? Yes, keep it. Is 15 > 12 × 1.1 = 13.2? Yes, keep it. Result ⟨10, 12, 15⟩.

trim(L, δ) scans a sorted list once. The first value is always kept. Any later value L[i] is dropped when it is at most last·(1+δ), where last is the most recently kept value, because last already represents it: last ≤ L[i] ≤ last·(1+δ).

Reading the pseudocode. Lines 1–3 keep the first value and remember it as last. Line 4 loops over the rest; line 5 is the decision "can last stand in for L[i]?"; lines 6–7 keep L[i] and make it the new last. Line 8 returns the shortened list.

Dart implementation. Index shift: the pseudocode's L[0]…L[m − 1] and loop for i from 1 to m − 1 are l[0]…l[m-1] and for (int i = 1; …); "m ← length of L" is l.length.

Maths → code. trim keeps a subsequence in which consecutive kept values differ by more than a factor 1 + δ, and every dropped value y has a kept z with z ≤ y ≤ (1 + δ)z. Hence at most log_1+δ(max) + 2 values survive.

Input size → what's feasible. |L| ≤ 10⁷ → one linear pass, Θ(|L|), instant.

Pitfall. The input must be sorted, and the comparison is against the last kept value, not the previous input value. Comparing neighbours would let a slowly rising chain (10, 10.5, 11, 11.5, …) be dropped one by one and drift arbitrarily far from every kept value.
Running time. Θ(m) for a list of m values: one pass, one comparison per value.

Stand-in guarantee. A dropped y satisfies y ≤ last·(1+δ) with last ≤ y, so z = last works in inequality y/(1+δ) ≤ z ≤ y. The proof table above computes the largest y/z over all dropped values for each example and compares it with 1+δ. After trimming, consecutive kept values differ by a factor greater than 1+δ, which is what bounds the length of a trimmed list (next section).

trim(L, δ): one pass; keep y only if y > last·(1+δ). Each dropped value has a kept value at most a factor (1+δ) below it. Θ(m) time.

approxSubsetSum (an FPTAS)

The procedure is exactSubsetSum plus one trim call per round with δ = ε/2n (n = number of numbers, ε = the accepted error). It returns z, the largest value in the final list; the guarantee is that the optimum t* satisfies t* ≤ (1+ε)·z. Because the running time is polynomial in n, ln t (the input length) and 1/ε, it is a FPTAS (fully polynomial-time approximation scheme). C15 covers the related pseudo-polynomial knapsack dynamic program.

Do the exact coin-total procedure, but after every coin, tidy the list with trim so nearly-equal totals collapse into one. The tidy-ups add a tiny error each time, and the trimming amount ε/2n is chosen so that n tidy-ups together still keep the answer within a factor (1+ε) of perfect.

Small example. S = ⟨130, 134, 180, 163⟩, t = 480, ε = 0.40 (so δ = 0.40 / 8 = 0.05): trimming merges nearby sums along the way, and the procedure returns z = 473 against the optimum 477 = 134 + 180 + 163. That is about 0.8% below the optimum, far inside the allowed 40%.

Reading the pseudocode. Same skeleton as exactSubsetSum with one new line 5 that trims the merged list by ε/2n before the over-target sums are dropped (line 6). Line 7 picks the largest surviving value z and line 8 returns it.

Dart implementation. Index shift: as in exactSubsetSum, the x_i disappear into a for-in loop; n is only needed for δ = ε/(2n).

Maths → code. The FPTAS guarantee, with δ = ε/2n: (a) the loop invariant that every achievable y ≤ t keeps a representative z in L_i with y/(1 + δ)ⁱ ≤ z ≤ y; (b) (1 + ε/2n)ⁿ ≤ 1 + ε so OPT ≤ (1 + ε)z; (c) |L_i| ≤ log_1+δ t + 2 = O(n ln t / ε), so the time is O(n² ln t / ε).

Input size → what's feasible. n = 500, t = 10⁹, ε = 0.1 → lists have at most 2·500·ln(10⁹)/0.1 ≈ 2·10⁵ values and the whole run costs about n²·ln t/ε ≈ 5·10⁷ steps (well under a second); the exact algorithm at n = 500 would face up to 2⁵⁰⁰ sums.

Pitfall. δ must be ε/2n, not ε. Each of the n rounds can lose a factor (1+δ), and the losses multiply: n rounds of (1+ε) would compound to (1+ε)ⁿ, which is useless. Also z can be smaller than the optimum, never larger: trimming only removes sums, so every value in the list is a real subset sum ≤ t.

Why it is an FPTAS. By induction, every achievable sum y ≤ t has a representative z in L_i with y/(1+ε/2n)ⁱ ≤ z ≤ y. With i = n, (1+ε/2n)ⁿ ≤ e^ε/2 ≤ 1+ε, so the best kept value is within 1+ε of the optimum. After trimming, consecutive kept values differ by a factor greater than 1+ε/2n, and all values lie in [1, t], so |L_i| ≤ ln t / ln(1+ε/2n) + 2 ≤ 3n ln t / ε + 2, which is polynomial in n, ln t (the input length) and 1/ε. That is the "fully polynomial" part; the cost table above compares real list sizes with this bound.

approxSubsetSum: exactSubsetSum with trim(·, ε/2n) after every merge. Returns z with OPT ≤ (1+ε)z, lists stay of length O(n ln t / ε), total time O(n² ln t / ε): a FPTAS.

Quiz

Interview questions

Cheat sheet

Algorithm	Problem	Ratio	Time (best / average / worst)	Space	Key idea / lower bound on OPT	When to use
approxVertexCover	min vertex cover	2	Θ(V + E) best, average and worst (each edge handled once)	O(V + E)	Maximal matching: every cover needs one endpoint per matched edge	Need a fast, guaranteed cover on a huge graph
approxTspTour	metric TSP	2	Θ(V²) best, average and worst (array Prim on a complete graph)	O(V)	MST weight ≤ optimal tour; preorder shortcuts by triangle inequality	Distances obey the triangle inequality (maps, Euclidean)
greedySetCover	min set cover	H(d) ≤ ln \|X\| + 1	O(Σ\|S\|) with buckets; naive O(\|X\|·\|F\|·min(\|X\|,\|F\|)); no best/worst gap	O(Σ\|S\|)	Charge 1/(new elements) to each covered element	Covering with overlapping sets (sensors, tests, skills); no polynomial algorithm does asymptotically better unless P = NP
Random assignment	max-3SAT	8/7 expected	Θ(n + m) best, average and worst (Θ(n) to draw, Θ(m) to score)	O(n)	Each clause satisfied w.p. 7/8; linearity of expectation	Baseline for max SAT; quick warm start for local search
approxMinWeightVc	weighted vertex cover	2	LP solve (polynomial) + Θ(V) rounding; no best/worst gap	LP size	LP optimum ≤ integer optimum; round x̄ ≥ ½ up	Vertices have different costs, so unweighted matching does not apply
mergeLists	merge two sorted lists	exact	Θ(\|a\| + \|b\|) best, average and worst	O(\|a\| + \|b\|)	Two pointers; equal values kept once	Sub-step of the subset-sum procedures
exactSubsetSum	subset sum	1 (exact)	best Θ(n) (every number exceeds t, lists stay ⟨0⟩); worst O(2ⁿ); O(n·t) when t is small (pseudo-polynomial)	O(min(2ⁿ, t))	Merge shifted lists; drop sums above t	Small n, or small t (pseudo-polynomial)
trim	list compression	each dropped y within 1+δ of a kept z	Θ(m) best, average and worst	O(m)	Keep y only if y > last·(1+δ)	Shrink a sorted list of numbers when small relative error is fine
approxSubsetSum	subset sum	1 + ε (FPTAS)	O(n² ln t / ε) worst; typically far less since lists are usually shorter than the bound	O(n ln t / ε)	Trim with δ = ε/2n after every round	Big n or big t and a few percent error is acceptable