PTAS and FPTAS, in depth: approximation schemes, a trimming FPTAS, Graham's scheduling PTAS and the strong NP-hardness barrier

Definitions: PTAS, EPTAS and FPTAS

For a minimisation problem with optimum OPT, an algorithm A is a polynomial-time approximation scheme (PTAS) if, for every fixed ε > 0, A(I, ε) returns a solution of cost at most (1+ε)·OPT, and its running time is polynomial in the input size n for that fixed ε. For maximisation the guarantee is at least (1−ε)·OPT. The words "for that fixed ε" carry a lot: a running time of n^1/ε qualifies, even though ε = 0.01 then means n¹⁰⁰.

An EPTAS (efficient PTAS) moves ε out of the exponent: its time is f(1/ε)·n^c for a constant c. Here f can still be enormous, but the dependence on n stays fixed. A fully polynomial scheme (FPTAS) is polynomial in both n and 1/ε, for example O(n³/ε).

The best-known FPTAS is for 0/1 knapsack. It scales every profit down by K = ε·P_max/n, rounds down, and runs the exact profit-indexed dynamic program on the smaller numbers. Rounding loses at most nK = ε·P_max ≤ ε·OPT in total. The approximation algorithms overview builds it step by step. Below, the same idea is applied to a different object: instead of the input, it rounds the list of candidate solutions.

Three techniques behind almost every scheme

Nearly every scheme combines three techniques.

1. Round the input. Coarsen the numbers so only a polynomial number of distinct values remain, solve the coarse instance exactly, and bound the rounding loss in terms of OPT. The knapsack FPTAS works this way, and so does rounding large jobs to a few size classes in scheduling.
2. Trim the solution space. Run an exact algorithm that keeps a growing set of partial solutions, but after each step merge any two whose values are within a factor (1+δ). The set stays small, and errors compound to at most (1+δ)ⁿ, which a δ of about ε/2n keeps below 1+ε.
3. Split big from small, or partition space. Handle the few large items by brute force, since they determine the structure of the solution, and add the many small ones greedily, since they can only cost a little. Geometric and planar schemes partition the space instead. Baker's technique deletes every k-th layer of a planar graph and solves the pieces exactly. Arora's Euclidean TSP scheme uses randomly shifted quadtrees. The loss is bounded by an averaging argument over the possible shifts.

Large weighted sums suggest techniques 1 or 2; a few dominant items suggest technique 3; geometry suggests partitioning.

An FPTAS for subset sum by trimming

Subset sum as an optimisation problem: given positive integers x₁…x_n and a target t, find a subset with the largest sum not exceeding t. The exact algorithm keeps the list L of every reachable sum up to t. Each item adds a shifted copy of the list, so L can grow to 2ⁿ entries. The FPTAS trims L after every merge: walking the sorted list, it keeps a value only if it exceeds the last kept value by more than a factor (1+δ).

def approx_subset_sum(items, t, eps):
    # largest subset sum <= t, within a factor (1 + eps) of the optimum
    delta = eps / (2 * len(items))
    L = [0]
    for x in items:
        merged = sorted(set(L + [y + x for y in L]))
        trimmed, last = [], -1
        for y in merged:
            if last < 0 or y > last * (1 + delta):
                trimmed.append(y)       # y is not represented by 'last'
                last = y
        L = [y for y in trimmed if y <= t]
    return max(L)

print(approx_subset_sum([104, 102, 201, 101], 308, 0.40))   # 302; optimum is 307

Why it is correct. Every value dropped is within a factor (1+δ) of a kept value no larger than it. One trim therefore loses at most that factor, and n trims lose at most (1+δ)ⁿ = (1+ε/2n)ⁿ ≤ e^ε/2 ≤ 1+ε for ε ≤ 1. Why it is fast. Kept values grow by more than a factor (1+δ) each step and none exceeds t, so each list holds at most about log_1+δ t + 2 values, which is O(n·ln t/ε). The total time is O(n²·ln t/ε), polynomial in n, in 1/ε and in the bit length of t. The example is the standard textbook instance: with ε = 0.40 it returns 302 against an optimum of 307, inside the promised factor 1.4 and much better than it.

A PTAS for makespan scheduling

Makespan minimisation on identical machines (P||C_max): place n jobs with processing times p_j on m machines so that the most-loaded machine finishes as early as possible. It is NP-hard even for m = 2, because it contains partition. Ronald Graham's 1969 scheme fixes an integer k, schedules the k largest jobs optimally by exhaustive search, then assigns each remaining job to whichever machine is least loaded at that moment.

import heapq, itertools, math

def graham_ptas(jobs, m, eps):
    # (1 + eps)-approximate makespan on m identical machines; m is a fixed constant
    order = sorted(range(len(jobs)), key=lambda j: -jobs[j])
    k = min(len(jobs), m * math.ceil(1 / eps))
    big, small = order[:k], order[k:]
    best = None
    for assign in itertools.product(range(m), repeat=k):   # m**k candidates
        if assign and assign[0] != 0:                      # machines are interchangeable
            continue
        loads = [0] * m
        for j, mach in zip(big, assign):
            loads[mach] += jobs[j]
        if best is None or max(loads) < max(best[0]):
            best = (loads, assign)
    loads, assign = best
    schedule = dict(zip(big, assign))
    heap = [(load, i) for i, load in enumerate(loads)]
    heapq.heapify(heap)
    for j in small:                                        # greedy list scheduling
        load, i = heapq.heappop(heap)
        schedule[j] = i
        heapq.heappush(heap, (load + jobs[j], i))
    return max(load for load, _ in heap), schedule

The bound. Let job j be the job that finishes last. If j is one of the k big jobs, the makespan equals the optimal makespan of the big jobs, which is at most OPT. Otherwise j was placed on the least-loaded machine, so it started no later than (Σp − p_j)/m. That gives makespan ≤ Σp/m + (1−1/m)·p_j ≤ OPT + (1−1/m)·p_k+1. Among the k+1 largest jobs, some machine in any schedule holds at least 1+⌊k/m⌋ of them, each of size at least p_k+1, so OPT ≥ (1+⌊k/m⌋)·p_k+1. Together these give a ratio of at most 1 + (1−1/m)/(1+⌊k/m⌋). Choosing k = m·⌈1/ε⌉ makes the ratio below 1+ε. The running time is O(m^k + n log n): polynomial for fixed m and ε, but exponential in both. This is a PTAS in its plainest form.

For m in the input, Hochbaum and Shmoys (1987) gave a PTAS that guesses a target makespan, rounds big jobs to a few size classes and packs them by dynamic programming; later work made it an EPTAS.

Worked example: three machines, seven jobs

Take m = 3 machines and seven jobs with times 5, 5, 4, 4, 3, 3, 3. The total is 27, so OPT ≥ 9, and 9 is achievable: {5,4}, {5,4}, {3,3,3}. The longest-processing-time-first heuristic (LPT) places 5, 5, 4 on separate machines, then 4 on the machine holding 4 (load 8), then 3 and 3 on the two machines holding 5 (loads 8 and 8), and the last 3 anywhere: makespan 11, ratio 11/9 ≈ 1.22. This is the classic tight example for LPT's 4/3 − 1/(3m) bound.

The ε = 0.5 row teaches the most. The search finds the unique best schedule for the six largest jobs, {5,3}, {5,3}, {4,4}, with every machine at 8. That leaves no good place for the last 3, and the makespan is 11, exactly the guaranteed bound. A schedule of the big jobs with makespan 9 ({5,4}, {5,4}, {3,3}) would have left room. Optimising the big jobs alone is not the same as optimising the whole schedule. The guarantee is a worst case, and here the worst case occurred. In practice you would also run LPT and keep the better of the two results, since that costs almost nothing.

Strong NP-hardness: when no FPTAS can exist

Can every problem with a PTAS also have an FPTAS? Strong NP-hardness says no, and it lets you settle the question before designing anything. A problem is strongly NP-hard if it stays NP-hard even when every number in the input is bounded by a polynomial in n. Bin packing, 3-partition and makespan with m part of the input are strongly NP-hard. Knapsack, subset sum and makespan with fixed m are only weakly NP-hard: they have pseudo-polynomial exact algorithms.

The theorem. Suppose a problem is strongly NP-hard, has integer objective values, and has OPT bounded by a polynomial q(n, max number). Then it has no FPTAS unless P = NP. The proof takes one line. Run the FPTAS with ε = 1/(q+1). Any solution within (1+ε)·OPT then lies within less than 1 of OPT, so for integer values it is exact. The running time is polynomial in n and q, which is polynomial on the instances whose numbers are small. Those small-number instances are NP-hard by assumption.

So first ask whether a pseudo-polynomial dynamic program exists. If it does, an FPTAS is usually within reach; if not, aim for a PTAS or a constant ratio.

Bin packing shows that "no PTAS" can be a misleading verdict. The 3/2 barrier holds only because tiny instances (OPT = 2) are hard to tell apart from OPT = 3. The asymptotic scheme of Fernandez de la Vega and Lueker uses at most (1+ε)·OPT + 1 bins, which is almost as good when OPT is large.

Using schemes in practice

Schemes are more common in theory than in production code, for these reasons.

• Constants decide usability. An FPTAS is usually practical: in a local test the pure-Python subset-sum code above took about 4 s for 100 items and 25 s for 200 items at ε = 0.01, each within 0.01% of the target. A PTAS with time n^1/ε rarely is. In the scheduling example, ε = 0.1 with ten machines means 10¹⁰⁰ candidates.
• Report the a-posteriori gap. The guarantee bounds the worst case. You get a much sharper statement for free by computing a lower bound on the same instance, such as Σp/m and p_max for makespan, or the LP relaxation, and reporting cost/lower bound. A 1.3 guarantee often comes with a 1.01 measured gap.
• Anytime alternatives. For medium instances an integer programming solver with a time limit returns a solution and a proven gap at the same time, and it often beats a scheme in practice. Use the scheme when you need a guarantee that doesn't depend on solver luck, or when the instance is too large for the solver.
• Use exact arithmetic where the bound depends on comparisons; floating point can break the proof's invariants on large values.

Failure modes

• Treating ε as the typical error. It is an upper bound. Measure the actual gap before you tune ε.
• Ignoring the fixed parameters. Graham's scheme and the m-fixed FPTAS are polynomial only while m stays constant. A fleet with 1,000 machines is a different problem.
• Expecting an FPTAS for a strongly NP-hard problem. Run the strong-hardness check first and save a week of searching.

What to do next

1. Classify your problem: does an exact pseudo-polynomial dynamic program exist? If it does, look for an FPTAS; if not, check whether the problem is strongly NP-hard.
2. Implement the trimming FPTAS above and confirm the (1+ε) bound empirically against brute force on random instances of 15 to 20 items.
3. Run the makespan example, then add LPT as a fallback and keep the better result.
4. Add a lower bound to every approximate solver you ship, and log the measured gap.
5. Choose ε from what an error actually costs your users, then benchmark time at ε, ε/2 and 2ε.
6. Benchmark an integer programming solver on real instance sizes before committing.

Related reading: approximation algorithms, including the knapsack FPTAS, exact knapsack algorithms, NP-completeness and reductions, vertex cover approximation and multi-dimensional knapsack, which has a PTAS for fixed d but no FPTAS.