PTAS and FPTAS Approximation Schemes, in depth: turning an exact DP into an FPTAS by state trimming, the bin packing asymptotic scheme, and testing the guarantee

The state-trimming recipe

Many NP-hard problems with numbers in the input have exact DPs that are pseudo-polynomial: the number of distinct states grows with the magnitude of the numbers, not just their count. Woeginger's 2000 paper on when a DP formulation guarantees an FPTAS turned the standard trick into a recipe. Process the input one item at a time. A state is a vector of numbers, such as machine loads. Each item maps every state to a few successor states. At the end, read the objective off the best state.

The trimming step: choose Δ = 1 + ε/(2n). Cut each coordinate's range into boxes [Δⁱ, Δⁱ⁺¹). After each item, keep only one state per combination of boxes. Two states in the same box agree within a factor Δ on every coordinate. The number of boxes per coordinate is about log_Δ P, which is O((n/ε) log P) where P is the largest possible value, so the state count is polynomial in n, 1/ε and the input's bit length, for a fixed vector dimension.

Why the error stays bounded: follow the optimal solution's path through the exact DP. At each step the trimmed DP holds some state within factor Δ of the optimal path's state on every coordinate, provided the transitions are well behaved: adding the same nonnegative job length to two values that are within factor Δ of each other keeps them within factor Δ. Errors compound once per item, so after n items the factor is Δⁿ = (1 + ε/2n)ⁿ ≤ e^ε/2 ≤ 1 + ε for ε ≤ 1. The objective (maximum load) is also ratio preserving, so the final answer is within 1 + ε.

Check three conditions before applying the recipe to a new problem: transitions must be monotone and preserve ratios as above; the vector dimension must be a constant; and the logarithm of the largest value must be polynomial in the input size. Subtraction breaks the first condition, which is why the recipe does not apply to objectives such as minimising the difference between two sums.

Implementation: makespan on m machines

Scheduling n jobs on m identical machines to minimise the makespan, with m fixed, is weakly NP-hard even for m = 2. Its exact DP tracks the vector of machine loads. Here it is with trimming; deleting the box key gives back the exact DP.

import math

def trimmed_makespan(jobs, m, eps):
    """(1+eps)-approximate makespan on m identical machines, m a constant."""
    n = len(jobs)
    log_d = math.log(1 + eps / (2 * n))       # Delta = 1 + eps/(2n)

    def box(load):                             # geometric grid cell of one coordinate
        return -1 if load == 0 else math.floor(math.log(load) / log_d)

    states = {(0,) * m: ()}                    # load vector -> machine of each job so far
    for p in jobs:
        nxt = {}
        for loads, assign in states.items():
            for i in range(m):
                new = loads[:i] + (loads[i] + p,) + loads[i + 1:]
                key = tuple(box(x) for x in new)
                if key not in nxt or max(new) < max(nxt[key][0]):
                    nxt[key] = (new, assign + (i,))
        states = dict(nxt.values())            # one representative per cell
    loads, assign = min(states.items(), key=lambda kv: max(kv[0]))
    return max(loads), assign

The function returns the assignment as well as the value, so the answer carries a certificate you can recompute. Two implementation notes. Floating-point logarithms can put a value on the wrong side of a box boundary; that only changes which representative is kept, never feasibility, because the stored loads are exact integers. And the box key could be the exact load for small values, which keeps tiny instances exact for free.

Worked example: what trimming buys

We ran the code above on 18 random jobs with lengths up to 10⁹ and m = 2. The exact DP ends with 262,144 distinct load vectors, every one of the 2¹⁸ assignments, because large random numbers almost never collide. The trimmed DP kept 455 states at ε = 0.5 and 1,757 at ε = 0.1, and returned makespans within 1.0008 and 1.0004 of the exact optimum. Real error is usually far below ε, because the analysis assumes every trim lands the wrong way.

The reverse case teaches as much. With small job lengths the exact DP is already small, because many assignments share a load vector, and the grid merges almost nothing. The trimmed count never exceeds the exact count, since every kept state is a real one, but you pay a logarithm per coordinate per state for no gain, and the bound (n log P / ε)^m can be far above both. A scheme is a guarantee about growth, not a promise of speed on your inputs. Measure both. The knapsack DP deep dive shows the same weight-indexed versus value-indexed choice for knapsack.

Rounding and grouping for bin packing

Bin packing has no FPTAS and no ratio below 3/2 in the ordinary sense, because deciding whether a set fits in two bins is the partition problem. It does have an asymptotic scheme: for any fixed ε, at most (1 + 2ε) OPT + 1 bins, due to Fernandez de la Vega and Lueker (1981). The recipe has three moves.

1. Set small items aside. Items of size at most ε are packed last. Since every large item exceeds ε, a bin holds fewer than 1/ε of them.
2. Linear grouping. Sort the n_L large items in decreasing order and cut them into groups of k = ⌊ε² n_L⌋. Give each item of the first group its own bin. Round every other item up to the largest size in its group. Each rounded group is no larger than the group before it, so the rounded items fit wherever the previous group fits in an optimal packing: the rounded instance needs at most OPT bins. The first group costs k extra bins, and since OPT is at least the total size, which exceeds ε n_L, k is at most ε OPT.
3. Solve the rounded instance exactly. There are about 1/ε² distinct sizes and fewer than 1/ε items per bin, so the number of bin configurations is a constant for fixed ε. Search over them, then swap each rounded copy for its real, smaller item. Finally first-fit the small items: a new bin opens only when every bin is more than 1 − ε full.

Implementing the bin packing scheme

The exact step below uses memoised search over configurations. Production code solves the configuration linear program instead, as Karmarkar and Karp did; the memo is clear but only fast for small inputs.

import math
from functools import lru_cache

def first_fit(sizes, bins=()):
    bins = [list(b) for b in bins]
    loads = [sum(b) for b in bins]
    for s in sizes:
        for i, load in enumerate(loads):
            if load + s <= 1 + 1e-12:
                bins[i].append(s); loads[i] += s
                break
        else:
            bins.append([s]); loads.append(s)
    return bins

def exact_pack_types(types, counts):
    """Fewest bins for counts[t] items of size types[t]."""
    configs = []
    def gen(t, room, cur):                     # every multiset of types that fits one bin
        if t == len(types):
            if any(cur): configs.append(tuple(cur))
            return
        k = 0
        while k <= counts[t] and k * types[t] <= room + 1e-12:
            gen(t + 1, room - k * types[t], cur + [k]); k += 1
    gen(0, 1.0, [])

    @lru_cache(maxsize=None)
    def best(rem):
        if not any(rem): return 0, ()
        first = next(i for i, r in enumerate(rem) if r)   # some bin holds this type
        result = None
        for cfg in configs:
            if cfg[first] == 0 or any(c > r for c, r in zip(cfg, rem)): continue
            used, plan = best(tuple(r - c for r, c in zip(rem, cfg)))
            if result is None or used + 1 < result[0]:
                result = (used + 1, (cfg,) + plan)
        return result
    return best(tuple(counts))

def aptas(items, eps):
    large = sorted((s for s in items if s > eps), reverse=True)
    small = [s for s in items if s <= eps]
    k = max(1, math.floor(eps * eps * len(large)))
    groups = [large[i:i + k] for i in range(0, len(large), k)]
    bins = [[s] for s in (groups[0] if groups else [])]   # first group: own bins
    rest = groups[1:]
    if rest:
        types = [g[0] for g in rest]           # round up to the group maximum
        _, plan = exact_pack_types(types, [len(g) for g in rest])
        pools = [list(g) for g in rest]
        for cfg in plan:                        # real items replace rounded copies
            bins.append([pools[t].pop() for t, c in enumerate(cfg) for _ in range(c)])
    return first_fit(small, bins)

On 60 random items between 0.05 and 0.7 (total size 25.27) with ε = 0.3, this returned 27 bins. First-fit decreasing, a one-line heuristic, returned 26. That is not a bug. The guarantee is asymptotic: with k items in the first group set aside one per bin and an additive +1, the scheme only beats good heuristics on worst-case inputs or at scale. With 10,000 large items and ε = 0.1, k is 100 extra bins against an OPT of at least 1,000: a bounded 10 percent, with about 99 rounded sizes. Use schemes when you need the bound; use heuristics, checked against a lower bound, when you need the packing.

Testing a guarantee

Scheme code fails quietly: an off-by-one in Δ or a wrong rounding direction still returns plausible answers. The guarantee is a checkable property, so check it on every change against brute force on small instances.

import itertools, random

def brute_makespan(jobs, m):
    best = float("inf")
    for a in itertools.product(range(m), repeat=len(jobs)):
        loads = [0] * m
        for p, i in zip(jobs, a): loads[i] += p
        best = min(best, max(loads))
    return best

def test_scheme(trials=200, eps=0.2, seed=7):
    rng, worst = random.Random(seed), 1.0
    for _ in range(trials):
        jobs = [rng.randint(1, 1000) for _ in range(rng.randint(2, 9))]
        m = rng.choice([2, 3])
        got, assign = trimmed_makespan(jobs, m, eps)
        loads = [0] * m
        for p, i in zip(jobs, assign): loads[i] += p
        assert max(loads) == got                      # certificate matches claim
        opt = brute_makespan(jobs, m)
        assert got <= (1 + eps) * opt + 1e-9, (jobs, m, got, opt)
        worst = max(worst, got / opt)
    return worst

Our run of 200 trials at ε = 0.2 reported a worst ratio of 1.006. Log the worst ratio, not only pass or fail: a drift from 1.006 toward 1.2 after a refactor means the trimming has become sloppy even though tests still pass. For bin packing, check that every item appears exactly once, no bin exceeds 1, and the count is at most (1 + 2ε) × an exact or lower-bound value + 1.

Failure modes

• ε in the exponent. The bin-packing scheme is polynomial for fixed ε, but the configuration count explodes as ε shrinks. Budget by measuring, not by the big-O.
• Unbounded dimension. The trimming recipe needs a constant-length state vector. With m part of the input, makespan becomes strongly NP-hard and no FPTAS exists unless P = NP.
• Rounding the wrong way. Rounding sizes down instead of up produces packings that overflow when real items are swapped back. Assert feasibility on the real items.
• Additive terms on small instances. The +1 and the k reserved bins dominate when OPT is small, which is exactly where users notice.
• Float boundaries. In doubles 0.1 + 0.2 + 0.7 is 1.0 but 0.7 + 0.2 + 0.1 is 0.9999999999999999, so fit checks depend on order. Use integer sizes or one explicit tolerance everywhere.

Trade-offs

The broader map of approximation, including set cover and LP rounding, is in the approximation algorithms guide, and the hardness side in NP-completeness.

What to do next

1. For your problem, write the exact DP first and print its state count on real inputs.
2. Check the three trimming conditions: ratio-preserving monotone transitions, constant dimension, polynomial log of the largest value.
3. Add the geometric box key and compare state counts and answers for several ε.
4. Return a certificate (the assignment or packing) and recompute the objective from it.
5. Build the brute-force harness and log the worst observed ratio on every change.
6. Benchmark against the best simple heuristic before shipping the scheme.
7. If the dimension is not constant, look for a strong NP-hardness proof before trying more.