Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Average Sensitivity of Dynamic Programming   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.

26
The categories of this paper are: bayes-an
9
The categories of this paper are: nlin
3
The categories of this paper are: physics
37
The categories of this paper are: supr-con
34
The categories of this paper are: chem-ph
14
The categories of this paper are: math-ph
31
The categories of this paper are: ao-sci
16
The categories of this paper are: stat
13
The categories of this paper are: quant-ph
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol
17
The categories of this paper are: q-fin
8
The categories of this paper are: hep-ex
7
The categories of this paper are: hep-th
15
The categories of this paper are: nucl-ex
36
The categories of this paper are: cmp-lg