A PTAS for Non-Adaptive Stochastic Top-$k$ Sum under General Combinatorial Constraints

We study non-adaptive selection of a feasible set $S$ so as to maximize the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises when hiring a team of $k$ workers or when computing VCG welfare in an $\mathrm{\ell }$-unit auction. The main setting is a fixed-dimensional nonnegative packing family: the natural LP has $d=O(1)$ packing inequalities with binary coefficients. No single algorithm achieves a constant factor on every membership family (already at $k=1$). Given an $\alpha$-approximate max-sum oracle, a decreasing surplus search yields ratio $\alpha \mathrm{/}((1+\alpha )(1+\text{eps}))$ for every $k\ge 1$ (cuts included). Every fixed-$d$ packing family already has a deterministic max-sum PTAS, hence inherits that constant. The same signatures that drive the exact-sum scheme—occupancy histograms when $k=O(1\mathrm{/}{\text{eps}}^2)$, and a three-dimensional mixture-quantile type when $k=\mathrm{\Omega }(1\mathrm{/}{\text{eps}}^2)$—are realized by a packing LP rather than by exact-sum, after enumerating $n^{f(d,1\mathrm{/}\text{eps})}$ heavy items. The result is a PTAS for every $k\ge 1$ on every fixed-$d$ packing family, including binary one- and two-dimensional knapsack. In this packing setting the scheme is essentially optimal as a generic guarantee: there is no FPTAS that works for every such $\text{F}$ unless $P=NP$, and no EPTAS unless $W[1]=FPT$ (two-dimensional knapsack is a witness, already at $k=1$). A separate boundary is query-weight exact-sum, which includes DAG paths and matchings and is incomparable with fixed-$d$ packing. That oracle also yields a PTAS for every $k$, so $d$-dimensional packing is a useful taxonomy, not a partition of every family that admits a PTAS.