Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu

When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochasti…