Bellman principle and approximability Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
One (old but useful) reference along these lines is Woeginger's 1998 paper on the connection between DPs and approximability: 


  When Does a Dynamic Programming Formulation Guarantee the Existence
  of a Fully Polynomial Time Approximation Scheme (FPTAS)?