ABSTRACT
This chapter reviews the three general methods—rounding, interval partitioning, and separation—proposed by Sahni [1] 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. Both of these problems are known to be NP-hard and both are solvable in pseudopolynomial time using either dynamic programming or enumeration.
