Sensitivity Analysis of Submodular Function Maximization

Conor McMeel, Yuichi Yoshida

We study the recently introduced idea of worst-case sensitivity for monotone submodular maximization with cardinality constraint $k$, which captures the degree to which the output…