--- title: 'Approximation and Heuristic Methods' source: 'https://academia.sh/en/courses/theory-of-computation/approximation-and-heuristic-methods' course: 'Theory of Computation' language: en updated: '2026-08-17T18:08:28+00:00' license: 'CC BY-SA 4.0' --- # Approximation and Heuristic Methods Counting the cost of giving up an exact solution, and the course's closing: the greedy approximation finds the exact result on 5 of 20 examples, diverges on 15, with a worst relative loss of 0.0676. As the exhaustively searched element count rises from 0 to 8, diverging examples drop from 15 to 0 and steps rise from 240 to 35,956; at k=12 the method spends 553,948 steps, exceeding the oracle's 81,920. The course closing carries a ten-row budget table and the closing of the Computer Science curriculum. The previous lesson left three paths and left the third one open: giving up on an exact solution. This lesson counts that path's cost. On how many examples does an approximate solution find the exact result, how far off does it fall when it doesn't, and when the given budget is grown, does the loss really close. The problem measured is again subset sum, but its question changes. In the decision form, the question was "does some subset reach the target exactly." In the **optimization form**, the question is: **what is the largest subset sum not exceeding the target.** This form makes room for approximation, because now an answer can be **short**, not "wrong." - **CC48.** The **oracle** is exhaustive search: the largest sum not exceeding the target, found by seeing every subset. The oracle's correctness is **by definition**. - **CC49.** **Relative loss** is the oracle's value minus the approximation's value, divided by the oracle's value. Not the average — the **worst** relative loss is written down. - **CC50.** **Approximation ratio** is a bound **proven** for all inputs. **What this lesson measures is not the approximation ratio — it is the relative loss observed on 20 examples**, and the two are not used in the same sentence. - **CC51.** The approximate method is a **hybrid** method: exhaustive search is done on the largest k elements, and the rest are filled **greedily**. **k = 0** is pure greedy approximation, **k = n** turns into exhaustive search. - **CC52.** The **budget** is the exhaustively searched element count k, and it is swept: 0, 4, 8, 12. - **CC53.** A step is **one element examined**; for the oracle it is **one subset**. - **CC54.** The count of diverging examples and the relative loss are written **separately**. Diverging alone does not say **by how much**. - **CC55.** Examples come from the shared definition's generator: seed **20260218**, 20 examples, 12 numbers per example. There is no second seed. - **CC56.** If loss comes out zero at a budget, this does **not** mean that budget will find the exact result on every input. **Observation is not proof.** - **CC57.** In the input-size sweep, every row is a **separate batch**; rows are not extensions of one another, and no direction is read from a single row. - **CC58.** Loss is **not measured** at an input size where the oracle cannot be run. No number is written for an unmeasured range. ## What Loss Is Measured Against An approximate solution's quality can only be measured if an oracle exists. The Advanced Algorithms course built this method on the traveling salesman problem: the oracle finds the best tour by exact enumeration, and the gap is measured against it. The method is not retold, it is used directly — and the same limit applies here. **Loss cannot be measured on input the oracle cannot run**; all that exists is a generalization made from small input. The second distinction is terminological, and it is strict in this course. **Approximation ratio** is a bound that has been **proven**: it holds for every input and comes from a proof. **Relative loss** is a measured value: it is observed on specific examples. The worst relative loss over twenty examples coming out to 0.0676 does **not** say the approximation ratio is 0.0676; what the twenty-first example would give was not measured. ## The Budget Sweep The block below sweeps the budget given to the approximate method across four values and compares it against the oracle at each one. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): d = seed result = [] for _ in range(count): numbers = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 numbers.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 result.append({"numbers": numbers, "target": sum(numbers) // 3 + d % 7}) return result def oracle(numbers, target): """The largest subset sum not exceeding the target. Exhaustive search.""" n, best, steps = len(numbers), 0, 0 for mask in range(1 << n): steps += 1 t = sum(numbers[i] for i in range(n) if mask >> i & 1) if best < t <= target: best = t return best, steps def hybrid(numbers, target, k): """Exhaustive search on the largest k elements, the rest filled greedily. k=0 is pure greedy, k=n turns into exhaustive search. One step = one element examined.""" s = sorted(numbers, reverse=True) top, rest = s[:k], s[k:] best, steps = 0, 0 for mask in range(1 << k): t, valid = 0, True for i in range(k): steps += 1 if mask >> i & 1: t += top[i] if t > target: valid = False break if not valid: continue for x in rest: steps += 1 if t + x <= target: t += x best = max(best, t) return best, steps EX = examples() print("budget k exact diverge worst relative loss total steps") for k in (0, 4, 8, 12): exact = diverge = top = 0 worst = 0.0 for o in EX: e, _ = oracle(o["numbers"], o["target"]) y, a = hybrid(o["numbers"], o["target"], k) top += a if y == e: exact += 1 else: diverge += 1 worst = max(worst, (e - y) / e) print(f"{k:7d} {exact:9d} {diverge:7d} {round(worst, 4):19} {top:11d}") print() print("oracle (exhaustive search) total steps:", sum(oracle(o["numbers"], o["target"])[1] for o in EX)) ``` ``` budget k exact diverge worst relative loss total steps 0 5 15 0.0676 240 4 15 5 0.0125 2980 8 20 0 0.0 35956 12 20 0 0.0 553948 oracle (exhaustive search) total steps: 81920 ``` ## Reading the Loss Three numbers side by side. **Budget k=0**: pure greedy approximation finds the exact result on **5 of 20** examples, diverges on **15**, worst relative loss **0.0676**, and it does this in **240 steps**. The oracle spends **81,920 steps** for the same job. That is, with **341 times fewer** steps, a loss of under seven percent in the worst case. Growing the budget really does close the loss. **k=4**: diverging examples drop from 15 to **5**, worst loss from 0.0676 to **0.0125**; the cost is 2980 steps instead of 240. **k=8**: diverging examples **0**, loss **0**, cost **35,956 steps**. This is one of the clearest examples in this course of the budget sweep "changing everything." The last row carries a warning. **At k=12 the method spends 553,948 steps** — nearly seven times the oracle's 81,920. A heuristic whose budget has been grown all the way does not just turn into exhaustive search — it turns into an exhaustive search **more expensive than exhaustive search**, since it refills the remaining elements greedily for every mask. **Making an approximate method exact does not produce a good exact method.** The zeros in the k=8 row must also be read carefully. Zero loss was observed **on these 20 examples**. It was **not shown** that exhaustive search over eight elements will find the exact result on every input; the remaining four elements are filled greedily, and there is no argument that this filling will always give the best result. This course's third claim holds one last time here: **observation is not proof.** ## When Input Size Changes The 0.0125 loss in the k=4 row is a number taken at a single input size. The second sweep runs the same budget across three separate input sizes. Every row is a **separate batch**, generated for its own input size; the sixteen-number examples are not an extension of the twelve-number ones. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): d = seed result = [] for _ in range(count): numbers = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 numbers.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 result.append({"numbers": numbers, "target": sum(numbers) // 3 + d % 7}) return result def oracle(numbers, target): n, best, steps = len(numbers), 0, 0 for mask in range(1 << n): steps += 1 t = sum(numbers[i] for i in range(n) if mask >> i & 1) if best < t <= target: best = t return best, steps def hybrid(numbers, target, k): """Exhaustive search on the largest k elements, the rest filled greedily.""" s = sorted(numbers, reverse=True) top, rest = s[:k], s[k:] best, steps = 0, 0 for mask in range(1 << k): t, valid = 0, True for i in range(k): steps += 1 if mask >> i & 1: t += top[i] if t > target: valid = False break if not valid: continue for x in rest: steps += 1 if t + x <= target: t += x best = max(best, t) return best, steps print(" n exact worst relative loss hybrid steps oracle steps") for n in (8, 12, 16): exact, ya, ha = 0, 0, 0 worst = 0.0 for o in examples(n=n): e, a1 = oracle(o["numbers"], o["target"]) y, a2 = hybrid(o["numbers"], o["target"], 4) ha, ya = ha + a1, ya + a2 if y == e: exact += 1 else: worst = max(worst, (e - y) / e) print(f"{n:2d} {exact:9d} {round(worst, 4):19} {ya:14d} {ha:11d}") ``` ``` n exact worst relative loss hybrid steps oracle steps 8 19 0.0109 1620 5120 12 15 0.0125 2980 81920 16 19 0.0037 4690 1310720 ``` The two columns show two separate growth patterns. The approximation's steps are 1620, 2980, 4690: as input size doubles, they grow by less than double. The oracle's steps go from 5120 to **1,310,720**, that is, **256-fold**. At sixteen numbers the oracle spends **279 times** as many steps as the approximation, and this ratio grows by a factor of sixteen for every four numbers added. The loss column, though, is not regular: 0.0109, 0.0125, 0.0037. The count finding the exact result is also 19, 15, 19. This irregularity is expected, because each row is a separate batch, and no direction can be read from a single row. What **can** be read is smaller and more precise: **across every input size measured, loss stayed under one and a half percent**, and this sentence holds for the range between 8 and 16 numbers. The column on the right also says why this range is narrow. At twenty-four numbers the oracle must see **16,777,216** subsets; there, loss cannot be measured, because the exact result to compare against is not known. Every sentence written about an approximate solution's quality on large input either generalizes from a loss measured on small input, or rests on a proven approximation ratio; this lesson did the former and claims none of the latter. ## What the Heuristic Cannot Know There is one more limit beyond the measured loss, and it has no number. The approximate method **cannot know on its own** that it diverged on a given example. Running k=0 produces a number; whether that number is the oracle's number can only be known by **running the oracle**, and if the oracle can be run, there is no need for the approximation. Knowing that the diverging example count is 15 is not the same as knowing **which** 15 examples they are. The practical consequence of this is as follows. What must be written alongside an approximate solution when it is deployed is not the average loss but the **worst** loss, and the input range in which that loss was measured. In a report, the sentence "runs with one percent loss" says nothing unless the input size and the range in which the oracle could be run are written down with it. ## Summary - In optimization form, an answer can be short rather than wrong; shortness can only be measured with an oracle, and loss cannot be measured on input the oracle cannot run. - Pure greedy approximation finds the exact result on 5 of 20 examples, diverges on 15, with a worst relative loss of 0.0676 at a cost of 240 steps; the oracle spends 81,920 steps. - At budget k=4, diverging examples drop to 5 and loss to 0.0125; at k=8 both drop to 0, at a cost of 2980 and 35,956 steps. - At k=12 the method spends 553,948 steps, exceeding the oracle's 81,920: a heuristic whose budget is grown all the way does not yield a good exact method. - Observing zero loss is not proof that budget will find the exact result on every input; measured relative loss and a proven approximation ratio are separate things. - The approximate method cannot know on its own that it diverged; what must be written when it is deployed is the worst loss and the input range it was measured in. ## Course Wrap-Up The Theory of Computation course followed a single question across ten lessons: what does a finite budget answer, what can it not answer, and does growing the budget change this. The table below gathers each lesson's budget and both sides of that budget. The four rows for the Models of Computation topic are taken from their source lessons; the numbers are not fabricated. | Lesson | Budget | What the budget answers | What it cannot answer | |---|---|---|---| | Finite Automata | states 1–3, universe of 31 strings | 2, 26, and **1054** distinct languages | share of **0.0000004908** next to 2³¹ languages; at k=2, freezes at **26** past length 2 | | Context-Free Languages | states 1–5, length 2–10 | classes **4, 6, 8, 10, 12**; exact count gives smallest k of **5** at length 4 | that no fixed k suffices at **any** length cannot be measured; a three-line rule generates the entire target | | Turing Machine | steps 2–200, 20,736 machines | **9784** halt, longest run **6** steps | count never changes past budget 6; of the 10,952 that do not halt, **5040** are decided by proof, **5912** remain unknown | | Undecidability | steps 5–200, 1000 starting points | **7, 155, 569, 756, 1000** | at 5000 starting points the same budget fails to decide **9** of them; 1000/1000 halting is not proof | | Class P | step budget 12–10,000 | threshold 20/20 (12 steps), pair 20/20 (66 steps) | subset sum 7/20 at 100 steps; whether the problem is in P | | Class NP | step budget 13–10,000 | with a certificate 20/20, total 101 steps | solving gives 0/20 at 13 steps; how to find the witness | | NP-Complete and NP-Hard | step budget 15–10,000 | reduction 20/20, 300 steps, answer preserved | that partition is NP-complete; that every NP problem reduces to it | | co-NP and Relationships Between Classes | step budget 13–10,000 | structured no 20/20, 260 steps | unstructured no needed exhaustive search for 20/20; whether NP equals co-NP | | The P vs NP Question | step budget 13–10,000, input size 8–24 | meet-in-the-middle 1357 steps, 20/20 agree | whether the gap closes; the answer to the question | | Approximation and Heuristic Methods | k = 0, 4, 8, 12 | 5/20 exact at k=0, 20/20 exact at k=8 | that k=8 will be exact on every input; a proven approximation ratio | The right column is this course's actual product. Every number in the left column comes from a run; every row in the right column names the place the run **could not reach**. This is the course that shows where measurement ends. The Computer Science curriculum followed a single axis across eight courses: from the bit's representation in hardware (K01) to writing a program (K02), the layout of data (K03), measuring a method's cost (K04), sharing the machine (K05), showing the system (K06), comparing hard problems against an oracle (K07), and the limit of measurement (K08) — at every layer, cost was **counted**, and a cost not counted did not count as known. **Two debts owed by K07 are paid off in this course.** The first was the question "why is this problem hard," which the traveling salesman and Hamiltonian path lessons each referred forward to here in a separate section. The answer is not a proof but a **classification**: these problems' "yes" answer is cheaply verified with a short certificate (`02`), their difficulty is carried between them by cheap reductions (`03`), and the "no" answer does not accept the same discount (`04`). The names of these classes are NP, NP-complete, and NP-hard. The second was the question from K07's course closing: is not knowing anything better than **brute force** a fact about our knowledge, or a fact about the problems. This question has a name, and it is the **P vs NP question** (`05`). Its answer is not known. The debt is paid not by answering the question, but by **naming it correctly** and showing why it is not answered: measurement can count a method's steps; it cannot speak about every method. The next curriculum is **Linux and System Administration**, and it changes the ground under the discussion. Computer Science established and modeled concepts; Linux and System Administration takes up the same concepts' counterpart in a **running system**: the shell, the file system, processes, services, the network, and kernel interfaces. Computer Science's Processes and Threads topic modeled and counted processes and the file system; Linux and System Administration uses the same concepts at the **command** level. The first question fits this transition: what is the interface for talking to a system, and how far down does a command given at that interface descend.