Approximation of integer programming problems (what the author is talking about more precisely) is actually pretty well studied. From Wikipedia: > NP-hard prob

Approximation of integer programming problems (what the author is talking about more precisely) is actually pretty well studied. From Wikipedia: > NP-hard problems vary greatly in their approximability; some, such as the bin packing problem, can be approximated within any factor greater than 1 (such a family of approximation algorithms is often called a polynomial time approximation scheme or PTAS). Others are impossible to approximate within any constant, or even polynomial factor unless P = NP, such as the maximum clique problem. > NP-hard problems can often be expressed as integer programs (IP) and solved exactly in exponential time. Many approximation algorithms emerge from the linear programming relaxation of the integer program. It turns out that shortest paths finding (via Bellman-Ford), dynamic programming and linear programming are all interrelated. Figuring out how your linear program can be represented as some other problem, like shortest paths finding, directly yields to generic approximation.