Average sensitivity of the Knapsack Problem

Soh Kumabe, Yuichi Yoshida

In resource allocation, we often require that the output allocation of an algorithm is stable against input perturbation because frequent reallocation is costly and untrustworthy.…