Average Sensitivity of Dynamic Programming

Soh Kumabe, Yuichi Yoshida

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 for…