Approximation of integer programming problems (what the author is talking about more precisely) is actually pretty well studied. From Wikipedia:<p>&gt; 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.<p>&gt; 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.<p>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.