Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge decomposition

Gary L. Miller, Richard Peng, Russell Schwartz +1

Let $P=(P_1,P_2,\dots ,P_n)$, $P_i \in \field{R}$ for all $i$, be a signal and let $C$ be a constant. In this work our goal is to find a function $F:[n]\rightarrow \field{R}$ wh…