Title: Dynamic Programming with Failure Functions: A Geometric Approach

Speaker: Yihui Wang, Fudan Univ

Time/Date:  Friday, May 11, 11-12
Location: Room 3401

Abstract:

In this paper we discuss how to speed up the calculation
of a generic Dynamic Program (DP) in the form
$$C[i] = \min_{0 < r < i}  D_r + g(L_i-L_r)$$
where $D_r$ is dependent upon $C[1],\,  C[2],\, \ldots,\, C[r-1],$
$L_i$ is some non-decreasing weight function,
and $g(x)$ is a given ``failure'' function.

This general DP models many different problems in multiple
domains and has therefore been extensively studied.
In particular, calculating $C[n]$ should a-priori require
$O(n^2)$ time but, if $g(x)$ has special properties, e.g.,
it is concave, convex or some combination of convex/concave
pieces, various authors have shown that the time can be
dramatically reduced down to  ``almost'' linear and, in some
special cases,  completely linear. The ``almost'' is a term
involving the inverse Ackermann function.

In this paper we introduce a simple, new, geometric technique that,
in many cases, gets rid of the inverse Ackermann function.
allowing purely linear time calculation of $C[n]$.  This permits
removing  the inverse Ackermann function from many application
DP algorithms in the literature.  This new technique is a generic one
that also permits speeding up the running time of DPs that
are in slightly more general forms.