ABSTRACT
This chapter reviews the three general methods—rounding, interval partitioning, and separation—proposed by Sahni to transform pseudopolynomial-time algorithms into fully polynomial-time approximation schemes. The three methods, which generally apply to dynamic-programming and enumeration-type pseudopolynomial time algorithms, are illustrated using the 0/1-knapsack and multiconstrained shortest paths problems. Rounding up, rounding down, and random rounding are three possible strategies to construct the reduced instance. In each, we employ a rounding factor d(n,ϵ), where n is a measure of the problem size. For convenience, we abbreviate d(n,ϵ) as d. Unlike rounding, which reduces an instance to one that is easier to solve using a known pseudopolynomial time algorithm, in interval partitioning we work with the unreduced (original) instance. The original Bellman-Ford algorithm was proposed for graphs in which each edge has a single weight. The extension allows for multiple weight.
