CMP.8:11 - SoTA-Echoing

How should an approximation become an affordable algorithm with a selected error? Adopt the scaling-and-bound construction illustrated in MIT’s advanced algorithms notes on approximation schemes: connect rounding loss to the original objective and to the size of the resulting dynamic program. Sections :4.2–4.5 and :5.1 make those connections explicit. A direct unrounded computation is preferable when its state range is already affordable; the scaled construction deliberately accepts a weaker answer in return for a range controlled by ε.

The simple table is not the strongest known knapsack complexity result. Chen, Lian, Mao and Zhang, version 3, combine proximity and approximate profit-function composition to obtain a substantially stronger bound. Adapt the comparison lesson: retain the transparent table for a small construction or a suitable workload, but reconsider its representation and composition when its n³/ε cost becomes limiting. The stronger asymptotic result does not establish an implementation advantage for every small input. A competing scheme meeting the same output requirement at lower total application effort reopens that choice.

For the numerical branch, adopt Higham’s separation of conditioning and backward error in :4.4. Compared with increasing arithmetic precision without locating the error, a local stable reformulation can retain the answer with less work; :5.2 derives one such case. Backward error is useful only for the permitted perturbations and with the sensitivity needed by the output. A changed input uncertainty, output operation or arithmetic implementation reopens this numerical choice. These arguments do not rank the adequacy of the subject model.