Approximation and Heuristic Methods

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.

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.

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.