<p>One (old but useful) reference along these lines is Woeginger's 1998 paper on the connection between DPs and approximability: </p>

<blockquote>
  <p><a href="http://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901">When Does a Dynamic Programming Formulation Guarantee the Existence
  of a Fully Polynomial Time Approximation Scheme (FPTAS)?</a></p>
</blockquote>

CC BY-SA 3.0
2014-03-04T18:04:54.543Z
2014-03-04T18:04:54.543Z
Suresh Venkat
<p>Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?</p>

CC BY-SA 3.0
2014-03-04T20:55:26.800Z
[Bellman's optimality principle](http://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality)
R B
<cc.complexity-theory><approximation-algorithms><approximation-hardness><dynamic-programming>
Bellman principle and approximability
Bruglieri
# Bellman principle and approximability

(Asked by: username_0 on 2014-03-04)

Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness, dynamic-programming
> **Comments:**
> **username_1**: [Bellman's optimality principle](http://en.wikipedia.org/wiki/Bellman_equation#Bellman.27s_Principle_of_Optimality)  

---

## 1 answers

### Answer by username_2 on 2014-03-04. Score: 5

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)?](http://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901)


---

