skip to content

What does an FPTAS promise that a PTAS does not, once you tighten the accuracy parameter from ten percent to one percent?

level: middleimportance: should knowfreq 45%

answer

  1. both take an accuracy dial
  2. the question is what the dial costs
  3. eps in the exponent versus a factor
  4. polynomial in n and in 1/eps
  5. scaling and rounding shrink the table

basics

~20 s

Both schemes take an accuracy parameter and return a solution within that fraction of optimal. A PTAS is polynomial in the input size for each fixed accuracy, but its exponent may blow up as accuracy tightens; an FPTAS is polynomial in the input size and in the reciprocal of the accuracy together.

solid answer

~50 s

A **polynomial-time approximation scheme** takes a parameter `eps > 0` and guarantees a solution within a factor `1 + eps` for minimisation, or `1 - eps` for maximisation, running in time polynomial in `n` *for each fixed* `eps`. The catch is that `eps` may sit in the exponent: a running time like `n^(1/eps)` is a legitimate PTAS, and going from `eps = 0.1` to `eps = 0.01` moves you from `n^10` to `n^100`, which is polynomial and unusable. A **fully polynomial-time approximation scheme** is stronger: its running time is polynomial in `n` **and** in `1/eps` jointly, so tightening accuracy costs a polynomial factor rather than a new exponent. Knapsack-style problems admit an FPTAS by scaling and rounding the values, then solving the rounded instance exactly; the rounding loses at most `eps` of the optimum while shrinking the table to a size polynomial in `1/eps`.

code

pseudocode · 10 lines
pseudocode
scale = eps * max_value / n

for each item i:
    rounded[i] = floor(value[i] / scale)

# exact table indexed by total rounded value:
# sum(rounded) <= n * (max_value / scale) = n * n / eps
choice = exact_best_selection(rounded, weight, capacity)

return choice          # true value >= (1 - eps) * OPT

go deeper

for a junior

Know that a scheme takes an accuracy parameter and returns a solution within that fraction of optimal, and that the two named kinds differ in how expensive tightening the accuracy is.

for a middle

Explain the definitions precisely: polynomial in the input for each fixed accuracy, versus polynomial in the input and the reciprocal of the accuracy jointly. Give a running time like n^(1/eps) as the example that separates them.

for a senior

Show the engineering consequence. Ask where the accuracy parameter sits in the running time before quoting a scheme, and be ready to say what makes the rounding argument work and what blocks it.

for a principal

The call is which accuracy the business actually requires and whether the gain over a fixed constant factor is worth a scheme's complexity. A scheme at an accuracy nobody asked for buys nothing but risk.

## Two schemes, one parameter A single approximation ratio is a fixed promise: factor two, and that is the deal. A **scheme** replaces the fixed factor with a dial. You hand the algorithm an accuracy parameter `eps > 0`, and it returns a feasible solution within `(1 + eps)` of optimal for a minimisation objective, or `(1 - eps)` of optimal for a maximisation objective. The interesting question is never whether the dial exists; it is **what turning it costs**. - A **PTAS** (polynomial-time approximation scheme) is polynomial in the input size `n` *for every fixed* `eps`. The definition deliberately says nothing about how the running time depends on `eps`. - An **FPTAS** (fully polynomial-time approximation scheme) is polynomial in `n` **and** in `1/eps` at the same time — a single polynomial in two variables. ## Why the difference is not pedantry Because `eps` is fixed before the asymptotics are taken, a PTAS is allowed to hide `eps` in the exponent. | Running time | Is it a PTAS? | Is it an FPTAS? | Cost of `eps`: 0.1 to 0.01 | |---|---|---|---| | `n^(1/eps)` | yes | no | `n^10` becomes `n^100` | | `2^(1/eps) * n^2` | yes | no | the constant multiplies by roughly `2^90` | | `n^3 / eps` | yes | yes | ten times slower | | `n^2 * (1/eps)^2` | yes | yes | one hundred times slower | The first two rows are formally polynomial for each fixed accuracy and practically unrunnable at any accuracy worth asking for. That is exactly the gap the "fully" in FPTAS closes: with an FPTAS, halving the error multiplies the work by a constant-degree polynomial factor, so the dial is usable across its range. ## How the knapsack-style FPTAS is built The classic construction is worth understanding because it shows where the two variables in the running time come from. The exact algorithm for a value-maximising selection under a weight budget can be run with a table indexed by *achievable value* rather than by weight; its size is proportional to the sum of the item values, which is exponential in the input size when values are written in binary. The scheme attacks precisely that: 1. Choose a scale factor proportional to `eps` times the largest single value, divided by the number of items. 2. Divide every value by the scale and round down. Each item now loses less than one scale unit. 3. Solve the rounded instance **exactly** with the value-indexed table, which is now small because the rounded values are small. 4. Return that selection, evaluated at the original values. The error accounting is the whole trick: at most `n` items are selected, each losing under one scale unit, so the total loss is under `n` times the scale, which is `eps` times the largest value — and the largest single value is itself a lower bound on the optimum, since taking that item alone is feasible. So the answer is within `(1 - eps)` of optimal. The table size is polynomial in `n` and `1/eps`, which is where the second variable enters. ## What blocks an FPTAS An FPTAS is a strong object, and there is a clean structural reason many problems cannot have one. If a problem stays NP-hard even when all its numbers are written in **unary** — the property called **strong NP-hardness** — then for integer objectives bounded by a polynomial in the input size, an FPTAS would let you set `eps` small enough that the `(1 + eps)` window contains only the optimal value, turning the scheme into an exact polynomial-time algorithm. So no FPTAS exists for such problems unless P = NP. Knapsack-style selection escapes this because it is NP-hard only through the *magnitude* of its numbers, which is exactly what rounding attacks. The ladder of strength, from weakest to strongest guarantee: - a constant-factor approximation with a fixed ratio; - a PTAS: any accuracy you like, at a cost that may explode in the exponent; - an FPTAS: any accuracy you like, at a polynomial cost in the accuracy too; - an exact polynomial-time algorithm. ## Reading a claim in practice When a scheme is offered, ask two questions and you have characterised it. First, *where does `eps` appear in the running time* — in a coefficient, or in an exponent? Second, *what accuracy will actually be requested*? A PTAS whose exponent is `1/eps` is fine if the honest requirement is ten percent and the inputs are small, and useless at one percent. Quoting "there is a scheme for it" without the placement of `eps` is the vague answer an interviewer is probing for.

  • Why does rounding the values lose at most `eps` times the optimum rather than an unbounded amount?
    Each selected item loses less than one scale unit, and at most `n` items are selected, so the total loss is under `n * scale`, which the scale factor makes equal to `eps` times the largest single value. That largest value is itself achievable on its own, so it is a lower bound on the optimum, and the loss is therefore at most `eps * OPT`.
  • A problem is strongly NP-hard with integer costs bounded by a polynomial in the input size. What does that say about an FPTAS for it?
    There is none unless P = NP. With the objective polynomially bounded, choosing `eps` smaller than the reciprocal of that bound makes the `(1 + eps)` window admit only the optimal value, so the scheme would solve an NP-hard problem exactly in polynomial time. Rounding cannot help, because the hardness does not come from the magnitude of the numbers.
  • If a problem has a PTAS, can it also be APX-hard?
    Not unless P = NP. APX-hardness means every constant-factor-approximable problem reduces to it in a way that preserves approximability, and its standard consequence is that no PTAS exists unless P = NP. So a genuine PTAS and APX-hardness cannot coexist without collapsing the classes.

saying these in an interview costs you the question

  • Uses PTAS and FPTAS interchangeably, as if fully were decorative.
  • Thinks a PTAS must be practical because it is polynomial time.
  • Believes an FPTAS is exact, rather than within the requested fraction.
  • Claims rounding the numbers gives an FPTAS for any NP-hard problem.
  • Cannot say where the accuracy parameter sits in the running time.