Let one integer unit represent \(h=1/10\) of certified error. For an individual nonnegative error \(e\), choosing
Thus integer feasibility \(\sum w\le B\) implies the real bound \(\sum e\le hB\). This implication is checked before applying the exact option or tree recurrence.
Reading the drawing
Solid segments show the actual sums and dashed segments their ceiling envelopes. A sound integer budget can reject a feasible real assignment; rounding down can instead give a false certificate.
Drawing labels and data 9 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
actual error sum versus ceiling envelope
- error
- \(0\)
- \(1/10\)
- \(1/5\)
- budget
- \(7/50>1/10\)
- \(2/25\le1/10\)
- Both ceiling envelopes are \(h(1+1)=1/5\).
A false certificate and a conservative rejection
For errors \((3/50,2/25)\), rounding down assigns weights \((0,0)\) although their real sum is \(7/50>1/10\). Rounding up gives \((1,1)\) and correctly excludes the assignment from budget one.
Now change the errors to \((3/50,1/50)\). Their sum is \(2/25\le1/10\), but separate ceilings still give \((1,1)\). The integer model rejects a genuinely real-feasible assignment. Conservative rounding protects soundness; it need not preserve every optimum of the unquantized problem.
Why the complexity is pseudo polynomial
For a declared integer budget \(B\), a table has \(B+1\) possible exact-weight states. A direct merge checks at most \((B+1)^2\) state pairs. At \(B=255\), this means 256 states and 65,536 candidate pairs at a merge, even though the budget fits in eight binary digits.
With a bounded number of children, the paper's direct tree implementation therefore has quadratic budget dependence at each node. Polynomial dependence on the numerical value of \(B\) does not mean polynomial dependence on the binary input length. These are counts of declared states and pairs, not measured runtimes or claims that every state is reachable.
Read this as
The dynamic program is exact for its integer data. Conservative conversion and the numerical size of the budget are separate obligations that determine its accuracy and practical scale.