  When processing data with uncertainty, it is desirable that the output of the
algorithm is stable against small perturbations in the input. Varma and Yoshida
[SODA'21] recently formalized this idea and proposed the notion of average
sensitivity of algorithms, which is roughly speaking, the average Hamming
distance between solutions for the original input and that obtained by deleting
one element from the input, where the average is taken over the deleted
element.
  In this work, we consider average sensitivity of algorithms for problems that
can be solved by dynamic programming. We first present a
$(1-\delta)$-approximation algorithm for finding a maximum weight chain (MWC)
in a transitive directed acyclic graph with average sensitivity
$O(\delta^{-1}\log^3 n)$, where $n$ is the number of vertices in the graph. We
then show algorithms with small average sensitivity for various dynamic
programming problems by reducing them to the MWC problem while preserving
average sensitivity, including the longest increasing subsequence problem, the
interval scheduling problem, the longest common subsequence problem, the
longest palindromic subsequence problem, the knapsack problem with integral
weight, and the RNA folding problem. For the RNA folding problem, our reduction
is highly nontrivial because a naive reduction generates an exponentially large
graph, which only provides a trivial average sensitivity bound.
