Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
$\begingroup$
$\endgroup$
-
$\begingroup$ Bellman's optimality principle $\endgroup$ – R B Mar 4 '14 at 20:55
$\begingroup$
$\endgroup$
One (old but useful) reference along these lines is Woeginger's 1998 paper on the connection between DPs and approximability:
answered Mar 4 '14 at 18:04
