Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation Alan Kuhnle Abstract Large-scale subset selection asks for a small useful set of examples, features, sensors, seed users, or context passages from an enormous ground set. Submodular maximization is a canonical model for such diminishing-returns problems, but rapidly growing datasets make even linear-time algorithms ever costlier. We study containment pruning : first reduce the ground set to a smaller core P P , then require that P P contain a near-optimal feasible solution for every downstream budget up to k k . Prior work has formulated many heuristics, but the theoretical limits of this preprocessing problem are largely unknown. For monotone submodular objectives, we prove that 1 − 1 / e 1-1/e is tight: greedy achieves this containment factor, and no algorithm can beat it even with a larger pruning budget. For non-monotone objectives, we give the first 1 / 2 − ε 1/2-\varepsilon containment algorithms under cardinality constraints and extend the approach to knapsack constraints. This 1 / 2 1/2 factor exceeds the best known algorithmic ratio and the known hardness threshold for non-monotone maximization, showing that pruning can be provably easier than optimization. Empirically, pruning lets an exact IP solver run on the reduced MaxCut instance with a ≈ 620 × {\approx}620\times speedup, and proof-of-concept experiments on LLM context selection demonstrate the utility of non-monotone submodular proxies and our proposed containment algorithms. 1 Introduction Large-scale subset selection. Many machine-learning and data-analysis tasks ask for a small useful subset of a much larger ground set: seed users in a social network, sensors or experiment locations, predictive features, representative documents, or context passages for an LLM [ 10 , 11 , 12 , 40 , 21 , 22 ] . Submodular maximization is a canonical model for these problems because it captures diminishing returns: once a subset already covers a concept, feature, region, or piece of evidence, adding another similar item helps less. The ground sets in these applications keep growing: the NCBI Sequence Read Archive has sustained exponential growth for over a decade [ 43 , 44 ] , and machine-learning training corpora have grown at roughly 3.7\times per year [ 45 ] . Even theoretically efficient submodular algorithms cannot avoid this growth: in the value-oracle model they require at least linear time in the ground-set size [ 9 ] . Larger ground sets therefore mean more oracle queries, higher latency, and larger downstream solver instances. Why pruning can help. When the target solution size k is small compared with the ground-set size n , much of the data is often redundant or irrelevant. Documents may be near duplicates, features may become correlated after a few predictors are selected, retrieved passages may be distractors or paraphrases, and many graph vertices may have interchangeable marginal value. This suggests a two-stage workflow: first reduce the large ground set to a smaller core P\subseteq N , then run a more expensive optimizer on P alone. This idea appears in pruned submodularity graphs, multi-stage selection, candidate reduction, learned graph pruning, and many heuristics [ 26 , 36 , 35 , 13 , 27 , 28 , 29 , 19 ] . The key question is not whether pruning can speed up a particular implementation, but whether the pruned universe still contains high-quality feasible solutions for a downstream optimizer to find. Moreover, the allowable core size may be set by memory, latency, parallelism, or the largest instance an exact solver can handle. Following Nath and Kuhnle [ 19 ] , we study containment as a function of a pruning budget p\geq k , and ask for one core that supports every downstream target size k^{\prime}\leq k . Problem 1.1 (Budget-Range Submodular Pruning) . Given N , f\colon 2^{N}\to\mathbb{R}_{\geq 0} (submodular), and k\in\mathbb{N} , for a pruning budget p\geq k , find P\subseteq N with |P|\leq p such that \max_{T\subseteq P,\,|T|\leq k^{\prime}}f(T)\;\geq\;\alpha\cdot\mathrm{OPT}_{k^{\prime}},\qquad\forall\,k^{\prime}\leq k, where \mathrm{OPT}_{k^{\prime}}=\max_{|T|\leq k^{\prime}}f(T) . We call \alpha the containment factor . The pruning algorithm does not need to identify the final solution. It only has to output a smaller universe in which good solutions still exist. This distinction is what makes containment different from ordinary optimization. The gap. Existing pruning methods have largely been heuristic: pruned submodularity graphs [ 26 ] and learned policies such as GCOMB, LeNSE, and COMBHelper [ 27 , 28 , 29 ] reduce search spaces empirically, but do not give worst-case guarantees that a good downstream solution remains in the pruned set. The main theoretical exception is Nath and Kuhnle’s QuickPrune [ 19 ] , which achieves \alpha\geq 1/24-\varepsilon for monotone weakly submodular objectives under a knapsack constraint. Intuitively, pruning may be easier than direct optimization, as we are not required to find an optimal solution, merely to contain it; but the complexity of containment pruning is still unclear even for monotone submodular functions, and essentially open for non-monotone functions. We investigate this complexity directly: can larger pruning budgets beat the classical 1-1/e monotone barrier, and can non-monotone objectives admit constant-factor budget-range containment? 1.1 Contributions • Tight monotone pruning. We fully characterize monotone cardinality pruning: standard greedy gives simultaneous (1-1/e) -containment for every k^{\prime}\leq k [ 1 , 19 ] , and no algorithm can guarantee a larger factor for any pruning budget p\geq k , even when it may output any set P with |P|\leq p (Theorem 3.1 ). The hardness extends to monotone \gamma -weakly DR functions and yields the tight 1-\kappa/e curvature barrier (Corollary 3.3 ). We also give a near-linear threshold-greedy variant that obtains (1-1/e-\varepsilon) -containment with O(k/\varepsilon) elements and \tilde{O}(n/\varepsilon^{2}) value queries (Theorem C.1 ). • Non-monotone pruning at 1/2 . We give the first constant-factor budget-range containment guarantees for non-negative non-monotone submodular functions under cardinality constraints. Sequential disjoint greedy and a one-pass window method both approach \alpha=1/2 while preserving every budget k^{\prime}\leq k (Theorems 4.1 and 4.3 ). This factor strictly exceeds the best known non-monotone maximization ratio ( 0.401 [ 4 ] ) and the best possible optimization ratio under standard assumptions ( 0.478 [ 5 ] ). This is possible because containment only asks the pruned set to contain a good feasible solution, not to extract it. Thus, containment pruning is provably easier than optimization in this setting. • Extensions beyond cardinality. The non-monotone analysis extends to knapsack constraints via sequential disjoint density-greedy (Theorem 4.5 ). The split-item analysis gives (1/2-\varepsilon)\mathrm{OPT}_{B^{\prime}} minus an explicit boundary-fragment term for every budget B^{\prime}\leq B . This term accounts for the last density-greedy item crossing the budget boundary. Under a standard small-item condition, it is absorbed and the clean 1/2-\varepsilon guarantee is recovered (Corollary 4.6 ). The output has total cost O(B/\varepsilon) and uses O(n^{2}/\varepsilon) value queries. • Empirical validation. On MaxCut, pruning a G(300,4500) instance to p=50 vertices lets an exact IP solver finish in 0.19s instead of 120s, a {\approx}620\times speedup while preserving \alpha=1.000 . An adapted COMBHelper baseline is competitive on in-distribution random graphs but degrades on out-of-distribution SNAP graphs; our provable methods require no training data. For LLM context selection, 38.7\% of HotpotQA questions exhibit non-monotone context effects. A non-monotone proxy \hat{f}(S)=\mathrm{FL}(S)-\theta(|S|) shows promise as a context-selection objective: on a 50-question MuSiQue pilot, relevance-gated pruning improves gold-passage recall by +9.2 percentage points at k=10 . Question Setting Prior This paper Does extra pruning budget help? Monotone card. Greedy: 1-1/e at p=k 1-1/e for every p\geq k , with matching hardness Can pruning be faster? Monotone card. Greedy: O(nk) queries 1-1/e-\varepsilon with |P|=O(k/\varepsilon) and \tilde{O}(n/\varepsilon^{2}) queries Can we prune non-monotone objectives? Non-monotone card. No constant-factor budget-range guarantee 1/2-\varepsilon via sequential disjoint greedy or window pruning Can this extend beyond cardinality? Non-monotone knapsack No non-monotone guarantee; NK25 gives monotone weak-submodular 1/24 1/2-\varepsilon minus boundary term; clean under small items Table 1: Main theoretical results, organized by the questions they answer. Blue marks new contributions. The first row closes monotone cardinality pruning: extra pruning budget cannot beat greedy’s 1-1/e factor. For non-monotone cardinality, the gap between 1/2 and the inherited 1-1/e upper bound remains open; the knapsack result has the boundary-term caveat shown in the table, with a clean small-item corollary. Paper organization. Section 2 collects notation and background. Section 3 presents the monotone hardness result. Section 4 develops both non-monotone containment algorithms. Section 5 reports experiments on LLM context selection, MaxCut, and synthetic non-monotone instances. Section 6 discusses open problems. Appendix A compares containment with bicriteria approximation, composable coresets, streaming summaries, and two-stage optimization. 2 Preliminaries This section fixes notation and collects the density-dependent maximization bounds that serve as reference points throughout the paper. The two key quantities to keep in mind are the containment factor \alpha (how well a pruned set represents the full ground set) and the density c=k/n (which governs both the best achievable approximation and the composition bound of § 3 ). Readers familiar with submodular maximization may skim this section and refer back as needed. Let N be a finite ground set with |N|=n . A function f\colon 2^{N}\to\mathbb{R} is submodular if for all A\subseteq B\subseteq N and x\notin B , f(x\mid A)\geq f(x\mid B) , where f(x\mid A)=f(A\cup\{x\})-f(A) denotes the marginal gain. We assume f is non-negative; note that f(\emptyset)=0 is not required—our proofs carry f(\emptyset) explicitly where it appears. The function is monotone if f(A)\leq f(B) whenever A\subseteq B . For \gamma\in(0,1] , the function is \gamma -weakly DR (diminishing returns) if f(x\mid A)\geq\gamma\cdot f(x\mid B) for all A\subseteq B and x\notin B ; at \gamma=1 this is ordinary submodularity. The total curvature of a monotone function is \kappa=1-\min_{j\in N}f(j\mid N\setminus\{j\})/f(\{j\}) ; at \kappa=0 the function is modular. We write O for an optimal solution: O\in\arg\max_{|T|\leq k}f(T) , and \mathrm{OPT}=f(O) . The density of the constraint is c=k/n . 2.1 Known density-dependent results Monotone. The Measured Continuous Greedy (MCG)—a continuous-relaxation algorithm that iteratively pushes a fractional solution toward the multilinear extension’s gradient—achieves approximation ratio \alpha^{*}(c)=1-(1-c)^{1/c} at density c , which is tight (Feldman & Kuhnle [ 2 ] , Theorems 4–5). Concretely: \alpha^{*}(c)\to 1-1/e\approx 0.632 as c\to 0 , \alpha^{*}(1/2)\approx 0.750 , \alpha^{*}(0.9)\approx 0.935 , and \alpha^{*}(c)\to 1 as c\to 1 . This function governs the composition bound in § 3 and tells us how much “easier” maximization becomes as the pruned set shrinks the effective ground set. Non-monotone. Buchbinder, Feldman, Naor, and Schwartz (BFNS) [ 3 ] give the density-dependent bound \alpha^{*}_{\mathrm{nm}}(c)=\max\!\left\{\frac{1}{e}+0.004,\;\left(1+\frac{1}{2\sqrt{c(1-c)}}\right)^{\!-1}\right\}-o(1). Concretely, this function is nearly flat across the density regime relevant to pruning: \alpha^{*}_{\mathrm{nm}}(0.01)\approx 0.372 , \alpha^{*}_{\mathrm{nm}}(0.1)\approx 0.400 , \alpha^{*}_{\mathrm{nm}}(0.2)\approx 0.444 , rising to 1/2 at c=1/2 (tight by the symmetry gap [ 6 , 7 ] ). Buchbinder and Feldman [ 4 ] subsequently achieved 0.401 for all down-closed constraints (density-independent). The combined best is \max(0.401,\alpha^{*}_{\mathrm{nm}}(c)) . The strongest hardness is 0.478 due to Qi [ 5 ] , improving the earlier 0.491 of Gharan and Vondrák [ 6 ] . The small spread [0.401,0.5] across all densities is why the composition bound does essentially no work in the non-monotone setting (§ 4 ). One additional non-monotone baseline—the three-term CDG guarantee of [ 3 ] —is used only in the warm-start analysis and is stated in Appendix B . 3 Monotone Pruning Does extra budget help? The simplest way to analyze pruning is composition : prune to p elements, then run the best optimization algorithm on the pruned set. If the pruned set has containment factor \alpha and the optimizer has approximation ratio \alpha^{*}(k/p) , the combined guarantee is at most \alpha\cdot\alpha^{*}(k/p) . Since this cannot exceed the information-theoretic limit on the original problem, we obtain \alpha\leq\alpha^{*}(k/n)/\alpha^{*}(k/p) . At p=k this recovers \alpha\leq 1-1/e , but it weakens as p grows. The following theorem resolves the remaining question directly: extra budget truly cannot help. Theorem 3.1 (Pruning Hardness for Monotone \gamma -Weakly DR Functions) . For every \gamma\in(0,1] , every \varepsilon>0 , and every polynomial C(\cdot) , there exists k_{0}=k_{0}(\gamma,\varepsilon,C) such that for all k\geq k_{0} and every p\geq k : no (possibly randomized) algorithm making at most C(|N|) value queries and outputting P\subseteq N with |P|\leq p can guarantee \mathbb{E}\!\left[\max_{S\subseteq P,\,|S|\leq k}f(S)\right]>(1-e^{-\gamma}+\varepsilon)\cdot\mathrm{OPT}_{k} for all monotone \gamma -weakly DR f\colon 2^{N}\to\mathbb{R}_{\geq 0} with |N|=\lceil 60p/\varepsilon\rceil . At \gamma=1 (full submodularity), this recovers the tight bound \alpha\leq 1-1/e . In particular, extra budget beyond k provably does not improve the containment factor for any constant or growing multiple of k . Proof sketch (full proof in Appendix E ). The core idea is a cancellation that neutralizes extra budget. We set |N|=\lceil 3p/\varepsilon^{\prime}\rceil and plant a random optimum \tilde{T} of size k using the construction of Harshaw et al. [ 16 ] . Any algorithm’s output P (with |P|\leq p ) is indistinguishable from the null instance, so P is effectively fixed before \tilde{T} is drawn. The expected overlap is then at most \mathbb{E}[|P\cap\tilde{T}|]\leq pk/|N|\leq\varepsilon^{\prime}k/3 , which is independent of p : the pruning-budget factor in the numerator cancels with the one in the denominator ( |N|\propto p ). A concentration bound shows that with high probability, P has too little overlap with \tilde{T} for any k -subset of P to beat the null-instance value 1-e^{-\gamma}+O(\varepsilon) . ∎ Remark 3.2 . The proof uses two separate hypergeometric tails. First, along the null-instance transcript, every query is hidden unless it has unusually large overlap with the random planted set; a two-regime bound covers both p=O(k) and p\gg k . Second, after the null transcript fixes the output P , the expected overlap \mathbb{E}[|P\cap\tilde{T}|]\leq\varepsilon^{\prime}k/3 is independent of p . Thus the extra budget cancels in the hiding argument rather than revealing more of the planted optimum. Real-world submodular functions—coverage, influence, facility location—often have total curvature \kappa<1 , meaning elements retain marginal value even in the presence of many others. For maximization, low curvature yields strictly better approximation ( 1-\kappa/e vs. 1-1/e ). One might hope that low curvature similarly helps pruning. The next result shows it does not: greedy at p=k is already optimal for every curvature level. Corollary 3.3 (Pruning Hardness with Bounded Total Curvature) . Let \kappa\in(0,1] denote total curvature: \kappa=1-\min_{j\in N}f(j\mid N\setminus\{j\})/f(j) . For every p\geq k and every \varepsilon>0 , no algorithm using polynomially many value queries can prune to p elements with containment \alpha>1-\kappa/e+\varepsilon for all monotone submodular functions with total curvature at most \kappa . Since the algorithm of Sviridenko, Vondrák & Ward [ 18 ] achieves \alpha=1-\kappa/e , this bound is tight. ( At \kappa=0 the function is modular, so exact containment is trivial. ) Proof. See Appendix F . ∎ For general monotone submodular functions, greedy achieves 1-1/e and the hardness matches it at every pruning budget p\geq k . Table 4 (Appendix F ) records how this compares with the composition benchmark. Remark 3.4 (Fast budget-range pruning) . Standard greedy attains \alpha=1-1/e in O(nk) queries via its prefix property [ 19 ] . A small-budget grid plus a geometric sweep of O((1+\log k)/\varepsilon) calls to the threshold greedy of [ 38 ] achieves exact-size (1-1/e-\varepsilon) -containment for all k^{\prime}\leq k simultaneously, with |P|=O(k/\varepsilon) and \tilde{O}(n/\varepsilon^{2}) total queries (Theorem C.1 , Appendix C ). The proof first obtains a slightly oversized witness and then thins it to size k^{\prime} ; monotone submodularity loses only an O(\varepsilon) multiplicative factor. 4 Non-Monotone Pruning Why composition fails for non-monotone functions. In the monotone setting, composition at least gives the right answer at p=k (even though it fails at larger budgets). For non-monotone objectives, composition is nearly useless even at p=k . The reason is that non-monotone approximation ratios barely change with density: the best ratio ranges from 0.401 at low density to 0.5 at high density. Since the numerator and denominator of the composition bound \alpha\leq\alpha^{*}_{\mathrm{nm}}(k/n)/\alpha^{*}_{\mathrm{nm}}(k/p) are nearly equal, the bound stays close to 1 for moderate pruning budgets and approaches the vacuous bound 1 as p grows. Entirely new techniques are needed. Can we prune non-monotone functions? We show that O(k) elements suffice for 1/2 -factor containment. For the top budget k , storing the output of the 0.401 -approximation of [ 4 ] gives only a single-budget optimization baseline; our guarantee is budget-range containment. Theorem 4.1 (Universal 1/2 Containment) . Let f be a non-negative submodular function on ground set N , and let k\leq n . For any \varepsilon>0 , there exists a set G\subseteq N with |G|=O(k/\varepsilon) such that for every k^{\prime}\leq k , (if |N|<\lceil 1/\varepsilon\rceil k , take G=N ; containment is exact and |G|<\lceil 1/\varepsilon\rceil k=O(k/\varepsilon) ) \max_{T\subseteq G,\,|T|\leq k^{\prime}}f(T)\;\geq\;\left(\tfrac{1}{2}-\varepsilon\right)\cdot\mathrm{OPT}_{k^{\prime}}, where \mathrm{OPT}_{k^{\prime}}=\max_{|S|\leq k^{\prime}}f(S) . Moreover, G can be constructed in O(nk/\varepsilon) oracle queries ( \ell=\lceil 1/\varepsilon\rceil greedy passes, each scanning O(n) elements at k steps). Proof sketch (full proof in Appendix G ). Construction. Run \ell independent greedy runs G_{1},\ldots,G_{\ell} , each of size k , on disjoint portions of the ground set. The pruned set is G=\bigcup_{i}G_{i} with |G|=\ell k . Some optimal elements may lie outside G ; call these \hat{O}=O\setminus G (“missed” elements, b=|\hat{O}| ), and let A_{i} be the first b elements of each greedy run i . Averaging. Because the runs are disjoint, their collective “damage” to f(O) is bounded: the total loss \sum_{i}[f(O)-f(O\cup A_{i})] is at most f(O) . By averaging, some run i^{*} satisfies f(O\cup A_{i^{*}})\geq(1-1/\ell)f(O) . Greedy domination. The key insight is that greedy run i^{*} had access to the missed elements \hat{O} as candidates but chose A_{i^{*}} instead. So each greedy pick has marginal gain at least as large as the corresponding missed element. Telescoping this chain gives 2f(A)-f(\emptyset)\geq f(\hat{O}\cup A) : the greedy prefix captures at least half the value of the prefix augmented with the missed elements. Combining. A submodularity decomposition yields \max(f(A),f(\dot{O}\cup A))\geq(1-1/\ell)f(O)/2 , where \dot{O}=O\cap G is the part of OPT already in G . Both candidates are feasible subsets of G with size at most k^{\prime} , giving \alpha\geq(1/2)(1-1/\ell) . The argument applies uniformly to every target budget k^{\prime}\leq k . ∎ Remark 4.2 (Where the 1/2 comes from, and why it is robust) . The 1/2 factor arises from two tight ingredients: (a) the greedy domination bound 2f(A)-f(\emptyset)\geq f(\hat{O}\cup A) , where the non-monotone marginal chain only gives a factor of 2 (vs. the (1-1/e)^{-1} one gets for monotone); and (b) the \max\geq\mathrm{sum}/2 split in the final step. Neither bound depends on |G| , so the 1/2 is robust to increasing the pruning budget—with pruning budget p=\ell k , the containment factor is \frac{1}{2}(1-1/\ell) : \ell=2 gives \alpha\geq 1/4 , while \ell\to\infty recovers 1/2 . Note this is not bicriteria: both candidate solutions A and \dot{O}\cup A satisfy |T|\leq k , improving over the bicriteria result of Feldman and Kuhnle [ 2 ] ( (1/2-\varepsilon) with output size \sim 1.44k ). The 1/2 is reminiscent of the unconstrained non-monotone hardness of [ 8 ] , but the analogy is suggestive rather than exact, and closing the gap to 1-1/e remains open (§ 6 ). A natural warm-start approach via the BFNS continuous double greedy [ 3 ] peaks at 4/9\approx 0.444 and cannot beat 1/2 ; see Appendix I for details. A second proof via window containment. Sequential disjoint greedy requires \ell independent passes over the ground set. We now give a structurally distinct proof of 1/2 -containment using a single-pass window algorithm (Algorithm 1 , Appendix J ) that achieves the same factor with a larger accumulated-window output. At each step, we maintain a window W_{t} of the top- \omega k elements by marginal gain and pick one uniformly at random; the window parameter \omega\geq 1 controls the width of exploration (larger \omega means a wider pool of candidates per step, at the cost of retaining all windows and hence a larger pruned set of size at most k+\omega k^{2} ). This simultaneously guarantees domination (every window element has marginal gain at least as large as any non-window element, so a random pick dominates any missed OPT element) and degradation control (the OPT value is not destroyed by the elements we commit to: \mathbb{E}[f(O\cup S_{m})]\geq e^{-1/\omega}f(O) ). Theorem 4.3 (Window Containment — Unconditional) . For any non-negative submodular f and window parameter \omega\geq 1 , Algorithm 1 returns an accumulated-window set P_{k}\subseteq N with |P_{k}|\leq k+\omega k^{2} such that, for every k^{\prime}\leq k , \mathbb{E}\!\left[\max_{|T|\leq k^{\prime},\;T\subseteq P_{k}}f(T)\right]\;\geq\;\frac{e^{-1/\omega}}{2}\cdot\mathrm{OPT}_{k^{\prime}}\qquad\text{(asymptotically as $k\to\infty$)}. The finite- k lower bound from the proof is (1-1/(\omega k))^{k}/2=e^{-1/\omega}\bigl(1-O(1/(\omega^{2}k))\bigr)/2 ; in particular, \alpha\to 1/2 as \omega\to\infty . Total query complexity: O(nk) . Full proof in Appendix J ; see Table 5 there for the guarantee as a function of \omega (at \omega=5 , \alpha\geq 0.410>0.401 ). Remark 4.4 (Window Pruning) . Window containment is structurally distinct from sequential disjoint greedy (Theorem 4.1 ): it makes a single wide-exploration pass rather than \ell independent narrow searches. Both converge to the same 1/2 barrier, suggesting it may be a fundamental limit. Knapsack extension. The SDG argument extends beyond cardinality constraints to knapsack constraints, where each element u has a positive cost p_{u} and a feasible solution must have total cost at most B . (We assume p_{u}\leq B for every element, since items too expensive to use alone can be discarded.) The key change is replacing greedy—which picks the element with the highest marginal gain—by density-greedy , which picks the element with the highest value-per-unit-cost : at each step, select u maximizing f(u\mid A)/p_{u} , and keep it if adding it stays within cost 3B . Running \ell disjoint density-greedy passes (with dummy zero-value items to fill each run to cost 2B , following [ 2 ] ) produces the pruned set. Theorem 4.5 (Knapsack budget-range containment) . For any \varepsilon\in(0,1/2) , sequential disjoint density-greedy with \ell=\lceil 1/\varepsilon\rceil runs produces a set P\subseteq N with c(P)\leq 3\ell B=O(B/\varepsilon) such that for every B^{\prime}\in(0,B] there exists Q\subseteq P with c(Q)\;\leq\;B^{\prime},\qquad f(Q)\;\geq\;\left(\tfrac{1}{2}-\varepsilon\right)\mathrm{OPT}_{B^{\prime}}\;-\;\Delta_{B^{\prime}}, where \Delta_{B^{\prime}}\geq 0 is a boundary-fragment loss that arises when the density-greedy prefix crosses the budget threshold mid-item. When no item is split, \Delta_{B^{\prime}}=0 . Total query complexity: O(n^{2}\ell)=O(n^{2}/\varepsilon) ( \ell adaptive density-greedy runs, each scanning O(n) candidates per step). The boundary term \Delta_{B^{\prime}} arises when the density-greedy prefix “overshoots” the budget—the last item added may cost more than the remaining budget allows. In that case, only a fraction \gamma of the item’s value is captured, and the remaining value is lost. Formally, \Delta_{B^{\prime}}=\gamma_{i^{\star}}f(\{a_{j^{\star}}^{(i^{\star})}\}) , where a_{j^{\star}}^{(i^{\star})} is the item that crosses the budget boundary; see Appendix D for precise definitions. The split item may cost more than B^{\prime} itself, so \Delta_{B^{\prime}} cannot be bounded simply by the value of the best affordable item. Corollary 4.6 (Small-item knapsack containment) . Fix a budget range \mathcal{B}\subseteq(0,B] and let B_{\min}=\inf\mathcal{B}>0 . Run sequential disjoint density-greedy with a sufficiently small internal accuracy parameter. Suppose that the item sizes are small at the density prefix scale used in the proof: for every B^{\prime}\in\mathcal{B} , if the proof for B^{\prime} selects a split boundary item a_{j^{\star}}^{(i^{\star})} with residual outside-core cost \beta=c(O\setminus P) , then p_{a_{j^{\star}}^{(i^{\star})}}\leq\eta\beta. In particular, this is the usual no-large-items regime when the relevant residual prefixes have cost comparable to the query budget; over a fixed range it is ensured by p_{\max}\leq\eta B_{\min} together with \beta=\Omega(B_{\min}) for the budgets under consideration. There is a universal constant C such that, if \eta\leq\varepsilon/C , then for every B^{\prime}\in\mathcal{B} there exists Q\subseteq P with c(Q)\leq B^{\prime},\qquad f(Q)\geq\left(\tfrac{1}{2}-\varepsilon\right)\mathrm{OPT}_{B^{\prime}}. The proof adapts the sequential disjoint greedy argument of Theorem 4.1 to density-greedy with item splitting, using the machinery of [ 2 ] . The proof sketch, simultaneous budget-range guarantee, knapsack hardness argument, and boundary-term discussion appear in Appendix D ; the full proof is in Appendix H.3 . 5 Experiments In this section, we ask whether containment cores are useful preprocessing objects. We show three messages. First, on MaxCut, our pruning algorithms usually retain an optimal or near-optimal k -cut and can shrink an exact IP solve by orders of magnitude. Second, on HotpotQA, LLM context selection is genuinely non-monotone: adding passages can hurt answer quality, and pruning a non-monotone proxy improves downstream F1/EM while using fewer passages. Third, on MuSiQue, the task has the containment structure pruning is designed for: keep evidence-bearing passages in a reduced pool while filtering distractors. We show that relevance-gated submodular diversity improves gold-passage recall over relevance ranking alone. Section 5.1 studies MaxCut on random and real-world graphs, including exact solving on pruned instances. Section 5.2 studies LLM context selection. Appendices L and M report COMBHelper details and synthetic separations. Unless stated otherwise, an algorithm receives a ground set \mathcal{N} , cardinality k , and pruning budget p=\omega k , outputs P with |P|\leq p , and then a k -subset is extracted from P by greedy or by exact IP. When exact optimization is feasible, the containment ratio is \alpha=f(S^{*}_{P})/\mathrm{OPT}_{k} , where S^{*}_{P} is the best k -set inside the pruned universe. When OPT is unavailable, we explicitly say which full-ground-set reference is used. Algorithms. We compare seven methods: SeqDisjoint (Theorem 4.1 ): \omega disjoint greedy runs of size k ; WindowMax / WindowRand : practical window heuristics with argmax / random selection from top- \omega k marginals; QuickPrune [ 19 ] : streaming threshold pruning (monotone only—no guarantee for non-monotone); StdGreedy : standard greedy for p steps; Random : uniform random p elements; COMBHelper [ 29 ] : a learned GNN pruning baseline, adapted to MaxCut; architecture, training, seed variance, and out-of-distribution behavior are deferred to Appendix L . 5.1 MaxCut on random and real-world graphs MaxCut asks whether pruning can preserve good solutions for a standard non-monotone objective. The objective is f(S)=|\{(u,v)\in E:u\in S,v\notin S\}| . It is non-monotone because adding a vertex can remove edges from the cut. We test on Erdős–Rényi random graphs G(n,m) , planted partition graphs, and SNAP social networks (Facebook, n=4039 , m=88{,}234 ). For the small instances in Table 2 , OPT is computed exactly via integer programming (CBC). For the larger SNAP instances, OPT is estimated by greedy on the full ground set, so reported \alpha values are upper bounds on the true containment ratio rather than certified guarantees. The table also includes COMBHelper on its in-distribution Erdős–Rényi setting; we defer its teacher/student split and transfer behavior to the appendix. Random G(100,1000) , k=15 Planted (200,20) Algorithm \omega=2 \omega=3 \omega=5 \omega=2 \omega=3 \omega=5 SeqDisjoint 0.997 1.000 1.000 1.000 1.000 1.000 WindowMax 1.000 0.999 1.000 1.000 1.000 1.000 WindowRand 0.975 0.967 0.984 0.988 0.983 0.982 QuickPrune 0.868 0.878 0.853 0.865 0.876 0.874 StdGreedy 0.997 1.000 1.000 1.000 1.000 1.000 COMBHelper † 0.997 1.000 1.000 – – – Random 0.877 0.921 0.966 0.699 0.805 0.902 Table 2: MaxCut containment on small instances, where exact IP gives the true denominator \mathrm{OPT}_{k} . SeqDisjoint (Thm 4.1 ) and WindowMax consistently achieve \alpha\geq 0.99 , far above the worst-case 1/2 guarantee. Results are stable across graph topologies: over 5 ER seeds, SeqDisjoint and WindowMax have mean \alpha\geq 0.996 (std \leq 0.004 ), while the random baseline has std in [0.013,0.040] . COMBHelper † is the adapted learned baseline on the ER setting; teacher and student give the same values there, so we show one compact row and defer the full learned-pruning comparison to Appendix L . QuickPrune, designed for monotone functions, plateaus at \alpha\approx 0.87 regardless of budget: once the non-monotone marginal sequence turns negative, its streaming threshold accepts too few elements ( |P|\approx 18\text{--}27\ll p ). SNAP social networks and exact solving. The same pattern persists on larger graphs, but the interpretation changes. On Facebook ( n=4039 ) and Wiki-Vote ( n=7115 ) with k=50 , exact OPT is unavailable; using the full-ground-set greedy solution as the reference, SeqDisjoint, WindowMax, and StdGreedy all obtain ratio 1.000 at every tested budget, while QuickPrune plateaus near 0.87 (details in Appendix L ). These are empirical ratios against the greedy reference, not certified OPT ratios. Pruning also reduces solver size. On a medium instance G(300,4500) with k=25 , where full IP still finishes, solving MaxCut on the full graph takes 120 s. After SeqDisjoint pruning to p=50 vertices ( \omega=2 ), the same IP solve on the reduced instance takes 0.19 s—a {\approx}620\times speedup with \alpha=1.000 . Baselines and separations. COMBHelper is competitive in distribution, but it is a learned baseline that requires exact training labels; Appendix L gives the teacher/student results, seed-variance check, and out-of-distribution SNAP comparison. The appendix also reports synthetic interference-coverage instances where SeqDisjoint contains the true optimum more often than a single greedy run (78% vs. 60% at n=20 , k=3 , \omega=2 ; Appendix M ). 5.2 Non-monotone LLM context selection This subsection separates two roles for LLM context selection. HotpotQA tests whether context selection is genuinely non-monotone and whether a cheap submodular proxy can guide pruning toward higher-quality reader inputs. MuSiQue then tests the containment claim: when supporting evidence is dispersed across hops, a pruner should keep evidence-bearing passages available for a downstream selector or reader rather than output the final context itself. Adding context passages to an LLM prompt initially improves answer quality but degrades it beyond a threshold—the “lost in the middle” effect [ 24 , 25 ] . This makes context selection a natural source of non-monotone objectives: more candidate passages can improve coverage, but more prompt context can also dilute attention or introduce distracting evidence. A non-monotone submodular proxy. We introduce a non-monotone submodular proxy \hat{f}(S)=\mathrm{FL}(S)-\theta(|S|) , where \mathrm{FL} is facility location on TF-IDF passage similarities and \theta is a convex, non-decreasing penalty fitted via isotonic regression from LLM evaluation data. Departing from prior submodular-LLM work [ 21 , 22 , 23 , 40 ] , which uses monotone facility location exclusively, our proxy captures the empirically observed quality degradation from context overload. The function \hat{f} is submodular (proof in Appendix L ). HotpotQA proxy containment. We test on HotpotQA (distractor setting) with expanded ground sets of n=50 ( k=3 ) and n=500 ( k=5 ); setup details are in Appendix L . On the fitted proxy, SeqDisjoint and WindowMax achieve \alpha=1.0 at every budget (Table 7 , Appendix L ); a larger n=500 FL-only stress test in Appendix L shows that 50\times compression preserves FL containment \alpha=1.000 . Non-monotonicity prevalence and LLM validation. Among 200 HotpotQA questions evaluated with a local 120B-parameter LLM, 77/199=38.7\% have some shorter prefix with higher F1 than the full 10-passage context, confirming that non-monotonicity is common enough that monotone-only pruning can miss the relevant regime. To verify that proxy containment translates to real answer quality, we evaluate the final k -subsets with the LLM (Table 3 ). At \omega=2 ( p=6 ), proxy-guided greedy selects only k=3 passages yet achieves F1/EM =0.599/0.42 , surpassing the all-original baseline (F1/EM =0.556/0.40 , all 10 passages). This supports the proxy claim: pruning can remove distractors while preserving enough evidence for the reader. QuickPrune, which collapses on non-monotone inputs, scores only F1 =0.262 —no better than random. Relevance-gated passage selection (MuSiQue). HotpotQA supports the proxy claim, but its gold passages are highly query-salient (top- k TF-IDF already achieves {\sim}80\% gold recall). MuSiQue [ 42 ] stresses the harder setting: gold passages span different Wikipedia entities (BM25@5 gold recall only 39\% ), and 48% of questions require 3–4 supporting passages. We define a restricted facility-location (RFL) function that diversifies within the query-relevant neighborhood (Appendix L ). On a 50-question pilot, RFL with embedding-based gating achieves gold-passage recall of 0.740 at k=10 , versus 0.648 for top- k TF-IDF ( +9.2 percentage points; bootstrap 95% CI [+2.8,+15.5] percentage points, n=50 ); per- k breakdowns are in Appendix L . These experiments suggest that non-monotone submodular pruning is a viable approach to LLM context selection; a comprehensive study across tasks and reader models is future work (downstream F1 and reader saturation in Appendix L ). Algorithm F1 EM Proxy \alpha Gold/ k |P| Gold only 0.641 0.44 — 2.00 2 All original 0.556 0.40 — 2.00 10 StdGreedy ( \omega\!=\!2 ) 0.599 0.42 1.00 1.02 6 SeqDisjoint ( \omega\!=\!2 ) 0.595 0.40 1.00 1.02 6 SeqDisjoint ( \omega\!=\!5 ) 0.509 0.36 1.00 1.02 15 WindowMax ( \omega\!=\!5 ) 0.431 0.26 1.00 0.74 5.2 QuickPrune 0.262 0.12 0.84 0.36 1.1 Random 0.274 0.16 0.79 0.38 15 Table 3: LLM validation of proxy-guided pruning on HotpotQA ( n=50 , k=3 , 50 questions). Proxy \alpha is measured on \hat{f} ; F1/EM are computed by the LLM on the selected k -subsets, and Gold/ k is the average number of gold passages selected. Proxy-guided pruning at \omega=2 matches or exceeds the full-context baseline while using only k=3 passages. The gold-only oracle (F1 =0.641>0.556 ) confirms non-monotonicity of the true quality function. 6 Conclusion In this paper, we make substantial progress towards resolving the complexity of pruning for submodular maximization. Monotone containment is tight at 1-1/e : greedy achieves it and no algorithm can beat it, regardless of pruning budget (Theorem 3.1 ). For non-monotone functions, two independent algorithms achieve 1/2-\varepsilon containment under cardinality constraints (Theorems 4.1 , 4.3 ), with a knapsack extension (Theorem 4.5 ). Since 1/2 exceeds the best non-monotone maximization ratio ( 0.401 ) and the known hardness threshold ( 0.478 ), pruning is provably easier than optimization. Several open questions remain: the gap from [1/2,1-1/e] in the non-monotone setting, and tight algorithms for more sophisticated constraints in the monotone setting. Empirically, pruning let an exact IP solver run {\approx}620\times faster on a reduced MaxCut instance; LLM context selection exhibited genuinely non-monotone behavior in the HotpotQA study ( 38.7\% of questions), and a relevance-gated submodular proxy improved gold-passage recall by +9.2 percentage points on a 50-question MuSiQue pilot. Appendix A Additional Related Work Ground-set pruning. Nath and Kuhnle [ 19 ] introduced containment pruning and gave the first constant-factor guarantee ( \alpha\geq 1/24-\varepsilon ) for monotone, \gamma -weakly submodular functions under a knapsack constraint via QuickPrune . Zhou et al. [ 26 ] gave a heuristic ground-set reduction via “pruned submodularity graphs,” but without containment guarantees. Several learned approaches—GCOMB [ 27 ] , LeNSE [ 28 ] , and COMBHelper [ 29 ] —train pruning policies from data but likewise lack approximation guarantees; Nath and Kuhnle showed that QuickPrune empirically dominates them on the monotone benchmarks studied there. Bicriteria vs. containment. The bicriteria framework of Feldman and Kuhnle [ 2 ] outputs 1.44k elements containing a (1-1/e) -approximate solution . This differs from containment in three respects: (i) bicriteria finds a specific approximate solution, whereas containment guarantees that near-optimal solutions exist in the pruned set for downstream re-optimization; (ii) bicriteria relaxes the budget ( 1.44k vs. strict k ), whereas containment enforces |T|\leq k^{\prime} ; (iii) bicriteria targets a single budget, whereas our model requires containment at all k^{\prime}\leq k simultaneously. The two models are complementary: bicriteria is stronger when one approximate solution suffices, containment is stronger when the pruned set must support multiple downstream tasks or budgets. Coresets and distributed reduction. Composable coresets [ 33 , 34 ] reduce the ground set to O(k) elements for distributed submodular maximization. Mirrokni and Zadimoghaddam [ 33 ] achieve 1/3 -approximation for monotone functions by merging local greedy summaries—this can be viewed as fixed-budget containment. However, their guarantee holds for a single fixed k and monotone objectives only; our budget-range formulation requires containment at all k^{\prime}\leq k simultaneously, our 1/2 containment handles non-monotone functions, and our monotone bound 1-1/e is strictly stronger than 1/3 . Two-stage and streaming approaches. Balkanski et al. [ 35 ] study a two-stage model achieving \approx(1-1/e) -approximation, but their output is a solution , not a pruned universe with containment guarantees. Streaming algorithms similarly produce approximate solutions rather than pruned universes amenable to re-optimization: Sieve-Streaming [ 37 ] achieves (1/2-\varepsilon) , and the optimal streaming bound was established by Alaluf et al. [ 15 ] . Wei et al. [ 36 ] use cheap surrogate submodular functions for multi-round data selection—the “optimize a proxy, then solve downstream” paradigm that our LLM experiments instantiate with the non-monotone proxy \hat{f} . Hardness constructions. Our monotone lower bound uses the planted-set construction of Harshaw et al. [ 16 ] , which hides a planted optimal set in the ground set: until the query set crosses an overlap threshold, the function is indistinguishable from a null instance with no hidden structure. This makes planted-set constructions well-suited to pruning hardness, because any algorithm’s output looks random with respect to the hidden optimum. The key technical insight for our result is that scaling |N|\propto p makes the expected overlap between a p -element pruned set and the planted optimum independent of p , so extra budget provably does not help. This differs fundamentally from the symmetry gap technique [ 7 , 6 , 5 ] —the standard tool for submodular maximization hardness—which exploits group-invariance: the hard instance is a symmetrized function whose value depends only on a coarse orbit statistic (roughly, how the queried set distributes across a hidden partition of N ), so every orbit-balanced subset of sufficient size is near-optimal. Any pruning algorithm that retains an orbit-balanced slice of N —e.g., a uniform random O(k) -subset—thus achieves containment close to the maximization ratio, making symmetry-gap constructions unsuitable for pruning lower bounds. The curvature-dependent hardness of Sviridenko et al. [ 18 ] inspires Corollary 3.3 . Non-monotone submodular maximization. Our containment results sit within the non-monotone approximation landscape anchored by two numbers: the 0.401 -approximation of Buchbinder and Feldman [ 4 ] (best algorithm) and the 0.478 -hardness of Qi [ 5 ] (strongest lower bound). The 1/2 -hardness of Feige et al. [ 8 ] for unconstrained non-monotone maximization is suggestive—our two independent 1/2 -containment proofs match this threshold—but no formal reduction to the containment setting is known. Submodular optimization for NLP and LLMs. Lin and Bilmes [ 40 ] introduced facility-location functions for document summarization, establishing the submodular proxy paradigm. A growing line of work applies such proxies to LLM pipelines: Kumari et al. [ 21 ] for in-context example retrieval, BumbleBee [ 22 ] for KV-cache management, DELIFT [ 23 ] for instruction fine-tuning. All perform selection —choosing a single set of items to include—using monotone proxies, and none address what guarantees the pruning stage itself provides. Our work differs in two ways: we study pruning (reducing the ground set so that downstream solvers can find near-optimal solutions at any budget), and we introduce the first non-monotone proxy for context selection. Non-monotonicity in LLM context. Liu et al. [ 24 ] document the “lost in the middle” phenomenon—LLMs degrade when relevant information is buried in long contexts—and Du et al. [ 25 ] show that context length alone hurts performance even with perfect retrieval. These findings motivate our non-monotone proxy \hat{f}=\mathrm{FL}-\theta : the convex penalty \theta , fitted from LLM evaluations via isotonic regression, models the empirical quality degradation that monotone proxies cannot capture. Appendix B Deferred Preliminaries BFNS Continuous Double Greedy with warm start. For completeness, we state the three-term guarantee from the Continuous Double Greedy (CDG) of [ 3 ] , which we use in Appendix I to analyze a natural warm-start approach (and show it cannot beat 1/2 ): Theorem B.1 (BFNS Theorem 3.7, adapted) . For a non-negative submodular function g on a ground set of size n with cardinality constraint k , let v=n/k-1 and s=\sqrt{v} . CDG outputs a set D with |D|\leq k satisfying g(D)\;\geq\;\frac{2s}{(s+1)^{2}}\,g(\mathrm{OPT}_{g})\;+\;\frac{v}{(s+1)^{2}}\,g(\emptyset)\;+\;\frac{1}{(s+1)^{2}}\,g(N). In particular, at v=4 (density c=1/5 ), the coefficients on g(\mathrm{OPT}_{g}) and g(\emptyset) are both 4/9 . The g(\emptyset) term is normally zero for normalized functions, but becomes significant when CDG is applied to g(S)=f(S\cup A) for a “warm start” set A : then g(\emptyset)=f(A) , which can be large. Appendix C Fast Budget-Range Pruning The monotone hardness shows that \alpha=1-1/e is the information-theoretic ceiling, and standard greedy [ 1 ] attains it at |P|=k in O(nk) value queries by virtue of its prefix property [ 19 ] : the size- k^{\prime} prefix of greedy’s output achieves (1-1/e)\,\mathrm{OPT}_{k^{\prime}} for every k^{\prime}\leq k . For very large ground sets the O(nk) query cost is the bottleneck, so it is natural to ask whether budget-range containment at the full (1-1/e-\varepsilon) ratio is attainable with near-linear queries. A simple application of existing single-budget machinery answers this affirmatively. Let \textsc{ThresholdGreedy}(N,f,k^{\prime},\eta) denote Badanidiyuru and Vondrák’s decreasing-threshold algorithm [ 38 ] , which for monotone submodular f returns S with |S|\leq k^{\prime} , f(S)\geq(1-1/e-\eta)\,\mathrm{OPT}_{k^{\prime}} , and query complexity O((n/\eta)\log(n/\eta)) . Theorem C.1 (Fast budget-range pruning) . Let f\colon 2^{N}\to\mathbb{R}_{\geq 0} be monotone submodular, k\leq|N| , and \varepsilon\in(0,1/2) . Set \eta=\varepsilon/4 and \mathcal{K}=\{1,\ldots,\min\{k,\lceil 1/\eta\rceil\}\}\cup\{\min\{k,\lceil(1+\eta)^{j}\rceil\}:j=0,1,\ldots,\lceil\log_{1+\eta}k\rceil\}. let P\;=\;\bigcup_{q\in\mathcal{K}}S_{q},\qquad S_{q}\;=\;\textsc{ThresholdGreedy}(N,f,q,\eta). Then |P|=O(k/\varepsilon) , the construction uses \tilde{O}(n/\varepsilon^{2}) value queries, and for every k^{\prime}\leq k there exists Q\subseteq P with |Q|\leq k^{\prime} and f(Q)\;\geq\;(1-1/e-\varepsilon)\,\mathrm{OPT}_{k^{\prime}}. Proof overview. The proof uses two external tools and is otherwise a direct construction. Step 1: Threshold greedy (imported). Run Badanidiyuru & Vondrák’s decreasing-threshold algorithm [ 38 ] at a geometric grid of budgets. Its guarantee is stated in Fact C.2 below. Step 2: Rounding down (imported). When the witness S_{q} overshoots the target budget k^{\prime} , thin it to a random k^{\prime} -subset using the standard monotone-submodular random-subset bound (Fact C.3 ). Step 3: Union bound (original). The union of all threshold-greedy outputs has total size O(k/\varepsilon) and query cost \tilde{O}(n/\varepsilon^{2}) . Fact C.2 (ThresholdGreedy guarantee) . The decreasing-threshold greedy algorithm of Badanidiyuru and Vondrák [ 38 ] has the following guarantee. For monotone submodular f with cardinality constraint k^{\prime} and accuracy parameter \eta\in(0,1) , \textsc{ThresholdGreedy}(N,f,k^{\prime},\eta) returns S with |S|\leq k^{\prime} , f(S)\geq(1-1/e-\eta)\mathrm{OPT}_{k^{\prime}} , using O((n/\eta)\log(n/\eta)) value queries. Fact C.3 (Random-subset bound) . For monotone submodular functions, the following standard random-subset bound follows from Nemhauser and Wolsey [ 1 ] . Let f be monotone submodular and let S be a set of size s . If Q is a uniformly random q -subset of S with q\leq s , then \mathbb{E}[f(Q)]\geq(q/s)\,f(S) . Proof. Size. The exact small-budget part contributes at most O(\min\{k^{2},\eta^{-2}\}) , which is O(k/\eta) whether k\leq 1/\eta or k>1/\eta . The geometric part contributes \sum_{j}O((1+\eta)^{j})=O(k/\eta) . Thus |P|\leq\sum_{q\in\mathcal{K}}q=O(k/\eta)=O(k/\varepsilon) . Queries. There are O(\eta^{-1}+\log k/\eta) calls to ThresholdGreedy , each using O((n/\eta)\log(n/\eta)) queries, for a total of \tilde{O}(n/\eta^{2})=\tilde{O}(n/\varepsilon^{2}) . Containment. Fix k^{\prime}\leq k . By construction there is a q\in\mathcal{K} with k^{\prime}\leq q\leq(1+2\eta)k^{\prime} : if k^{\prime}\leq\lceil 1/\eta\rceil then take q=k^{\prime} , and otherwise take the first geometric budget at least k^{\prime} (the ceiling contributes at most \eta k^{\prime} ). By monotonicity of f , \mathrm{OPT}_{q}\geq\mathrm{OPT}_{k^{\prime}} , so Fact C.2 gives f(S_{q})\;\geq\;(1-1/e-\eta)\,\mathrm{OPT}_{q}\;\geq\;(1-1/e-\eta)\,\mathrm{OPT}_{k^{\prime}}. If |S_{q}|\leq k^{\prime} , take Q=S_{q} . Otherwise, let Q be a uniformly random k^{\prime} -subset of S_{q} . By Fact C.3 with s=|S_{q}| and q=k^{\prime} : \mathbb{E}[f(Q)]\;\geq\;\frac{k^{\prime}}{|S_{q}|}f(S_{q})\;\geq\;\frac{1}{1+2\eta}f(S_{q})\;\geq\;(1-2\eta)f(S_{q}). Therefore \mathbb{E}[f(Q)]\;\geq\;(1-2\eta)(1-1/e-\eta)\,\mathrm{OPT}_{k^{\prime}}\;\geq\;(1-1/e-\varepsilon)\,\mathrm{OPT}_{k^{\prime}}, where the last inequality uses \eta=\varepsilon/4 and \varepsilon\in(0,1/2) . Hence some realization of the thinning gives the claimed exact-size witness. ∎ Remark C.4 (Rounding down witnesses) . The thinning step is used only to certify exact-size containment. The pruning set itself still has size O(k/\varepsilon) ; whether one can achieve the same all-budget guarantee with a core of size O(k) and o(nk) queries remains open. Appendix D Knapsack Proof Sketch and Additional Remarks Proof sketch. This sketches Theorem 4.5 ; the full proof appears in Appendix H.3 . Fix a query budget B^{\prime}\in(0,B] and rerun the analysis for this budget. Let O be optimal for B^{\prime} , let \hat{O}=O\setminus P and \dot{O}=O\cap P , and set \beta=c(\hat{O})\leq B^{\prime} . If \beta=0 , then O\subseteq P and Q=O proves the claim. Assume \beta>0 . For each density-greedy run i , take the prefix whose cost is exactly \beta . If this prefix cuts through original item a_{j_{i}}^{(i)} , apply the split operation of Definition H.1 : write \tau_{i} for the included fragment of a_{j_{i}}^{(i)} and let the other fragment remain excluded. Thus A^{\prime}_{i} is a set in the split ground set with c(A^{\prime}_{i})=\beta ; it is either a real prefix or a real prefix plus the single included boundary fragment \tau_{i} . Let f^{*} be the resulting split extension, and write S^{\uparrow} for the full lift of an original set S . The sets A^{\prime}_{i} are disjoint, so the same averaging step as in Theorem 4.1 gives a run i^{\star} such that f^{*}(O^{\uparrow}\cup A^{\prime}_{i^{\star}})\geq(1-1/\ell)f(O). Set A=A^{\prime}_{i^{\star}} . Since every element of \hat{O} survives all previous runs and is therefore a candidate throughout run i^{\star} , the density-domination lemma (Lemma H.5 ) gives f^{*}(\hat{O}^{\uparrow}\cup A)\leq 2f^{*}(A)-f(\emptyset). Submodularity applied to \hat{O}^{\uparrow}\cup A and \dot{O}^{\uparrow}\cup A then implies \max\{f^{*}(A),\,f^{*}(\dot{O}^{\uparrow}\cup A)\}\geq(1/2-\varepsilon)\mathrm{OPT}_{B^{\prime}}. To report a real feasible subset, delete the included boundary fragment from A if one exists; call the resulting original set \widehat{A} . The candidates \widehat{A} and \dot{O}\cup\widehat{A} both have cost at most B^{\prime} . If the selected run has boundary fragment \tau_{i^{\star}} , let a_{j^{\star}}^{(i^{\star})} be the original item containing it and let \gamma_{i^{\star}} be the included fraction of that item. Deleting the fragment loses at most \Delta_{B^{\prime}}=\gamma_{i^{\star}}f(\{a_{j^{\star}}^{(i^{\star})}\}) ; if no split occurs, \Delta_{B^{\prime}}=0 . In the split case, the item a_{j^{\star}}^{(i^{\star})} is budget-specific, but it may still have p_{a_{j^{\star}}^{(i^{\star})}}>B^{\prime} , so this loss cannot in general be charged to the best feasible singleton at budget B^{\prime} . ∎ Remark D.1 (Simultaneous guarantee across budgets) . The pruned set P depends only on the master budget B , not on B^{\prime} ; for each B^{\prime}\in(0,B] , rerun the proof with that budget. The values \beta , the boundary fragments, and the averaged run i^{\star} may all change with B^{\prime} , but the underlying pruned set P is fixed. This extends the budget-range containment model of [ 19 ] (cardinality) to knapsack, with the explicit boundary-fragment loss in Theorem 4.5 . The item-splitting machinery is imported from Feldman and Kuhnle [ 2 ] , originally developed for their bicriteria knapsack algorithm; we restate the needed pieces self-contained in Appendix H and adapt the density-domination invariant to the source/target pair (\hat{O},A) rather than their (E_{2},E_{1}) . Remark D.2 (Knapsack hardness inherited from cardinality) . The monotone hardness of Theorem 3.1 ( 1-1/e for every pruning budget) transfers verbatim to knapsack: a unit-cost instance is a cardinality instance, so any knapsack pruning algorithm that beat the 1-1/e barrier would also beat it under cardinality—a contradiction. The same argument shows the non-monotone upper bound \leq 1-1/e holds for knapsack, placing all three settings in Table 1 within the gap [1/2,\,1-1/e] . Remark D.3 (Why the boundary term is explicit) . A tempting shortcut is to drop the boundary fragment and compare the lost value to the singleton value of the boundary item. This gives a clean singleton-style guarantee for a fixed budget when the boundary item is itself feasible for that budget. For a query budget B^{\prime} , however, the boundary item is simply the item that crosses the residual cost in the density order for the proof at B^{\prime} . It can have cost larger than B^{\prime} even though the included fragment has cost at most the residual budget, so the original item is not a feasible singleton witness. For this reason Theorem 4.5 keeps the boundary-fragment loss explicit instead of hiding it inside a best-feasible-singleton term. Appendix E Full Proof of Theorem 3.1 Theorem (Theorem 3.1 , restated) . For every \gamma\in(0,1] , every \varepsilon>0 , and every polynomial C(\cdot) , there exists k_{0}=k_{0}(\gamma,\varepsilon,C) such that for all k\geq k_{0} and every p\geq k : no (possibly randomized) algorithm making at most C(|N|) value queries and outputting P\subseteq N with |P|\leq p can guarantee \mathbb{E}\!\left[\max_{S\subseteq P,\,|S|\leq k}f(S)\right]>(1-e^{-\gamma}+\varepsilon)\cdot\mathrm{OPT}_{k} for all monotone \gamma -weakly DR f\colon 2^{N}\to\mathbb{R}_{\geq 0} with |N|=\lceil 60p/\varepsilon\rceil . At \gamma=1 (full submodularity), this recovers the tight bound \alpha\leq 1-1/e . The proof builds on the hard-instance family of Harshaw, Feldman, Ward & Karbasi [ 16 ] (hereafter HFWK). We first state the construction in the form used here, then give a proof overview that separates the HFWK import from our adaptations. Proposition (HFWK planted family, adapted form) . Fix \gamma\in(0,1] , \varepsilon^{\prime}\in(0,1/6) , and integers k\geq 1/\varepsilon^{\prime} and m\geq\lceil 3k/\varepsilon^{\prime}\rceil . Let \mathcal{N} be a ground set of size m and set g=\lceil\varepsilon^{\prime}k+3k^{2}/m\rceil . For every k -subset T\subseteq\mathcal{N} , the HFWK construction gives functions f_{T}\colon 2^{\mathcal{N}}\to\mathbb{R}_{\geq 0} that depend on T through the statistic t_{T}(S)=|S\setminus T|+\min\{g,|S\cap T|\}. The resulting family \{f_{T}\}_{T\in\binom{\mathcal{N}}{k}} satisfies: (P1) f_{T} is non-negative, monotone, and \gamma -weakly diminishing returns; (P2) f_{T}(S)\leq 1 for all S\subseteq\mathcal{N} , with equality when S=T ; (P3) f_{\varnothing}(S)\leq 1-e^{-\gamma}+12\varepsilon^{\prime} for all S with |S|\leq k ; (P4) f_{T}(S)=f_{\varnothing}(S) whenever |S\cap T|\leq g or |S|\geq 3k-g . The case m=\lceil 3k/\varepsilon^{\prime}\rceil is HFWK Proposition 14. The extension to any larger ground set is the adaptation used here: inspecting their proof shows that properties (P1)–(P4) use only m\geq 3k/\varepsilon^{\prime} ; no step requires equality. Proof overview. The proof of Theorem 3.1 proceeds in three steps. Setup. We import the HFWK planted family and properties (P1)–(P4), but instantiate it on an enlarged ground set with m=|\mathcal{N}|=\lceil 3p/\varepsilon^{\prime}\rceil instead of m=\lceil 3k/\varepsilon^{\prime}\rceil . The enlargement is our adaptation: it ensures that |P|\leq p\leq\varepsilon^{\prime}m/3 , making the p -cancellation below possible. Indistinguishability. We show that a polynomial-query algorithm cannot distinguish f_{\tilde{T}} from the null instance f_{\varnothing} with high probability, using a two-regime hypergeometric tail argument (Fact E.1 below) that covers both p=O(k) , where the additive tail suffices, and p\gg k , where the multiplicative tail is needed. This two-regime analysis is new; HFWK’s original argument handles only m=\Theta(k/\varepsilon^{\prime}) . Overlap bound. Since the algorithm’s output P is fixed by the null transcript, the expected overlap satisfies \mathbb{E}[|P\cap\tilde{T}|]\leq\frac{pk}{m}\leq\frac{\varepsilon^{\prime}k}{3}. The upper bound is independent of p because the p in the pruning budget cancels with the p in m=|\mathcal{N}|\propto p . Concentration shows the overlap stays below the threshold g , so property (P4) forces all k -subsets of P to match the null-instance value, bounded by (P3). The p -cancellation mechanism is the central insight: enlarging the ground set in proportion to the pruning budget neutralizes the additional budget, yielding a hardness bound that holds uniformly for all p\geq k . We state the concentration tools used throughout, then give the full proof. Fact E.1 (Hypergeometric concentration [ 17 ] ) . Let X\sim\mathrm{Hypergeometric}(m,K,n) , i.e., X counts marked items when drawing n items without replacement from a population of m containing K marked items. Write \mu=nK/m . (i) (Additive tail.) For every t>0 , \;\Pr[X-\mu\geq t]\leq\exp(-2t^{2}/n) . (ii) (Multiplicative tail.) For every integer a>\mu , \;\Pr[X\geq a]\leq(e\mu/a)^{a} . Both follow from Hoeffding’s Theorem 4, which shows that hypergeometric tails are dominated by binomial tails; bound (i) is then the standard sub-Gaussian tail, and (ii) is the Chernoff–Poisson bound applied to the dominating binomial. Fix \gamma\in(0,1] , p\geq k , and \varepsilon>0 . We may assume \varepsilon\leq 1 ; larger \varepsilon only weakens the target bound. Set \varepsilon^{\prime}=\varepsilon/20 , so \varepsilon^{\prime}\in(0,1/6) , and take k large enough that k\geq 1/\varepsilon^{\prime} , as required by the HFWK construction; this lower bound is absorbed into the theorem’s constant k_{0} . Set m=\lceil 3p/\varepsilon^{\prime}\rceil=\lceil 60p/\varepsilon\rceil . We instantiate the adapted HFWK family stated above on a ground set \mathcal{N} of size m . Since m\geq 3p/\varepsilon^{\prime}\geq 3k/\varepsilon^{\prime} , all properties (P1)–(P4) hold for this instance. The only quantity that changes relative to HFWK’s original setting is the overlap threshold g=\left\lceil\varepsilon^{\prime}k+\frac{3k^{2}}{m}\right\rceil\leq\left\lceil\varepsilon^{\prime}k\left(1+\frac{k}{p}\right)\right\rceil\leq 2\varepsilon^{\prime}k+1, where the last inequality uses k/p\leq 1 . By Yao’s minimax principle, it suffices to show the bound for deterministic algorithms against the uniform distribution over \{f_{\tilde{T}}\} , where \tilde{T} is a random k -subset of \mathcal{N} . Let Alg be a deterministic algorithm making at most C(|\mathcal{N}|) queries. Write C(x)\leq Ax^{d} for constants A,d and all x\geq 1 . Step 1: Indistinguishability. Goal: show that the algorithm cannot tell whether it is facing the null instance f_{\varnothing} (which has no planted optimum) or the real instance f_{\tilde{T}} (which does). If the algorithm cannot distinguish the two, its output P_{0} is the same in both cases, and any analysis under the null instance applies to the real one. When given f_{\varnothing} , Alg makes queries S_{1},\ldots,S_{\ell} ( \ell\leq C(|\mathcal{N}|) ) and outputs P_{0} with |P_{0}|\leq p . Fix any query set S on the null-instance transcript. If |S|\geq 3k-g (a large query), then f_{\tilde{T}}(S)=f_{\varnothing}(S) for every \tilde{T} by (P4)—the query is too large to reveal the planted set. Otherwise |S|<3k-g , so the query can differ only if the overlap X=|S\cap\tilde{T}| exceeds the threshold g . The random variable X is hypergeometric with mean \mu=k|S|/m . Since |S|<3k-g and g\geq\varepsilon^{\prime}k+3k^{2}/m , we have g/k-|S|/m\geq(\varepsilon^{\prime}+3k/m)-(3k-g)/m\geq\varepsilon^{\prime} , so the gap between g and the mean satisfies g-\mu\geq\varepsilon^{\prime}k . Fact E.1 (i) with t=\varepsilon^{\prime}k and n=k gives \Pr[X>g]\leq\exp(-2\varepsilon^{\prime 2}k). We also apply Fact E.1 (ii) with a=\lceil\varepsilon^{\prime}k\rceil : since |S|<3k and m\geq 3p/\varepsilon^{\prime} , \Pr[X>g]\leq\Pr[X\geq\varepsilon^{\prime}k]\leq\left(\frac{ek}{p}\right)^{\varepsilon^{\prime}k}. The two bounds complement each other across all pruning budgets. When p is small (at most 2ek ), the ground set is only O(k/\varepsilon^{\prime}) and the additive tail decays fast enough: C(|\mathcal{N}|)\exp(-2\varepsilon^{\prime 2}k)\leq\varepsilon/40 for sufficiently large k . When p is large ( p>2ek ), the multiplicative tail dominates because ek/p<1/2 : C(|\mathcal{N}|)\left(\frac{ek}{p}\right)^{\varepsilon^{\prime}k}\leq A\left(\frac{4p}{\varepsilon^{\prime}}\right)^{d}\left(\frac{ek}{p}\right)^{\varepsilon^{\prime}k}\leq\varepsilon/40 for sufficiently large k , uniformly over all p>2ek : writing r=p/k>2e , the middle expression is A(4/\varepsilon^{\prime})^{d}k^{d}r^{d}(e/r)^{\varepsilon^{\prime}k} , whose maximum over r>2e occurs at the boundary once \varepsilon^{\prime}k>d and then decays exponentially in k . By a union bound over the at most C(|\mathcal{N}|) null-transcript queries, the event \mathcal{E}=\bigl\{f_{\varnothing}(S_{i})=f_{\tilde{T}}(S_{i})\text{ for all }i=1,\ldots,\ell\bigr\} satisfies \Pr[\mathcal{E}]\geq 1-\varepsilon/40 for sufficiently large k . Under \mathcal{E} , every query returns the same value as under f_{\varnothing} , so Alg follows the same execution path and outputs P_{0} . Step 2: Overlap concentration. Goal: show that the algorithm’s output P_{0} has too little overlap with the planted optimum \tilde{T} to contain a good solution. Since Step 1 established that P_{0} is determined by the null transcript (independent of \tilde{T} ), the overlap |P_{0}\cap\tilde{T}| is hypergeometric with \mathbb{E}\bigl[|P_{0}\cap\tilde{T}|\bigr]=\frac{k\cdot|P_{0}|}{|\mathcal{N}|}\leq\frac{k\cdot p}{3p/\varepsilon^{\prime}}=\frac{\varepsilon^{\prime}k}{3}. Note that p cancels: the expected overlap is independent of the pruning budget. From the definition g=\lceil\varepsilon^{\prime}k+3k^{2}/|\mathcal{N}|\rceil\geq\varepsilon^{\prime}k (the ceiling dominates the first summand), the gap satisfies g-\mathbb{E}[|P_{0}\cap\tilde{T}|]\geq 2\varepsilon^{\prime}k/3 . By Fact E.1 (i) with n=k and t=2\varepsilon^{\prime}k/3 : \Pr\bigl[|P_{0}\cap\tilde{T}|>g\bigr]\;\leq\;e^{-2t^{2}/k}\;=\;e^{-8\varepsilon^{\prime 2}k/9}\;=\;e^{-\Omega(\varepsilon^{2}k)}\;\leq\;\varepsilon/20 for sufficiently large k . Step 3: Containment bound. Goal: combine Steps 1 and 2 to bound the expected containment. Define the good event \mathcal{G}=\mathcal{E}\cap\{|P_{0}\cap\tilde{T}|\leq g\} . By union bound, \Pr[\mathcal{G}]\geq 1-\varepsilon/10 . Under \mathcal{G} : • Alg outputs P_{0} (by \mathcal{E} ); • every S\subseteq P_{0} with |S|\leq k satisfies |S\cap\tilde{T}|\leq|P_{0}\cap\tilde{T}|\leq g , so f_{\tilde{T}}(S)=f_{\varnothing}(S) by (P4); • \max_{S\subseteq P_{0},\,|S|\leq k}f_{\tilde{T}}(S)=\max_{S\subseteq P_{0},\,|S|\leq k}f_{\varnothing}(S)\leq 1-e^{-\gamma}+12\varepsilon^{\prime} by (P3). Since \mathrm{OPT}=f_{\tilde{T}}(\tilde{T})=1 by (P2) and f_{\tilde{T}}(S)\leq 1 always: \displaystyle\mathbb{E}\!\left[\max_{S\subseteq P,\,|S|\leq k}f_{\tilde{T}}(S)\right] \displaystyle\leq\Pr[\mathcal{G}]\cdot(1-e^{-\gamma}+12\varepsilon^{\prime})+\Pr[\neg\mathcal{G}]\cdot 1 \displaystyle\leq(1-e^{-\gamma}+12\varepsilon^{\prime})+\varepsilon/10\;=\;1-e^{-\gamma}+\tfrac{7\varepsilon}{10}\;<\;1-e^{-\gamma}+\varepsilon. Appendix F Proof of Corollary 3.3 Corollary (Corollary 3.3 , restated) . Let \kappa\in(0,1] denote total curvature: \kappa=1-\min_{j\in N}f(j\mid N\setminus\{j\})/f(j) . For every p\geq k and every \varepsilon>0 , no algorithm using polynomially many value queries can prune to p elements with containment \alpha>1-\kappa/e+\varepsilon for all monotone submodular functions with total curvature at most \kappa . Since the algorithm of Sviridenko, Vondrák & Ward [ 18 ] achieves \alpha=1-\kappa/e , this bound is tight. (At \kappa=0 the function is modular, so exact containment is trivial.) Proof overview. The proof is a two-step reduction. Step 1: SVW augmentation (imported). Sviridenko, Vondrák & Ward [ 18 ] show that augmenting the normalized planted-optimum family used in their curvature lower bound with a linear term produces controlled curvature without altering the information-theoretic landscape (Fact F.1 below). Step 2: Transfer from Theorem 3.1 (original). Because the linear term depends only on |A| , it carries no information about the planted set T ; the indistinguishability and overlap arguments from Theorem 3.1 transfer directly. Fact F.1 (SVW curvature augmentation) . In the normalized form used by Sviridenko, Vondrák, and Ward [ 18 ] , the curvature augmentation has the following form. Let \{f_{T}\} be a planted-optimum family on ground set \mathcal{N} in the normalization used by the SVW lower bound, with f_{T}(T)=k\,p_{\max} and p_{\max}=\max_{i}f_{T}(\{i\}) . For \kappa\in(0,1] , define \hat{f}_{T}(A)=f_{T}(A)+\frac{1-\kappa}{\kappa}\,|A|\,p_{\max} . Then: (i) \hat{f}_{T} is monotone submodular with total curvature \leq\kappa ; (ii) \hat{f}_{T}(T)=k\,p_{\max}/\kappa ; (iii) the linear term is determined by |A| alone and therefore provides no information about T . Proof of Corollary 3.3 . Step 1 (SVW augmentation). Apply Fact F.1 to the HFWK family from Theorem 3.1 with the same enlarged ground set m=\lceil 3p/\varepsilon^{\prime}\rceil . The resulting \hat{f}_{T} has curvature \leq\kappa . Step 2 (Transfer from Theorem 3.1 ). By Fact F.1 (iii), the linear term carries no information about the planted set. All queries on \hat{f}_{T} reduce to queries on f_{T} plus a cardinality lookup, so the indistinguishability and overlap concentration arguments from Theorem 3.1 apply unchanged. Under the good event (overlap below g ), every k -subset S\subseteq P satisfies \hat{f}_{T}(S)\;\leq\;(1-1/e+O(\varepsilon))\,k\,p_{\max}+\tfrac{1-\kappa}{\kappa}\,k\,p_{\max}\;=\;\tfrac{1-\kappa/e+O(\varepsilon)}{\kappa}\,k\,p_{\max}, while \hat{f}_{T}(T)=k\,p_{\max}/\kappa by Fact F.1 (ii). The ratio is 1-\kappa/e+O(\varepsilon) . ∎ p c^{\prime}=k/p Composition \alpha\leq Hardness \alpha\leq Best algo \alpha Status k 1 1-1/e 1-1/e 1-1/e Tight 2k 1/2 0.843 1-1/e 1-1/e Tight ck (fixed c>1 ) 1/c (1-1/e)/\alpha^{*}(1/c) 1-1/e 1-1/e Tight \omega(k) \to 0 \to 1 1-1/e 1-1/e Tight Table 4: Monotone containment landscape at \gamma=1 (full submodularity). The composition column is the benchmark obtained by “prune then optimize”; it matches 1-1/e only at p=k and weakens for larger pruning budgets (approaching 1 only when p/k grows). The hardness and best-algorithm columns show that the true monotone containment factor remains exactly 1-1/e for every p\geq k . For \gamma -weakly DR functions, replace 1-1/e with 1-e^{-\gamma} ; for curvature \kappa , use 1-\kappa/e (Corollary 3.3 ). Appendix G Full Proof of Theorem 4.1 Theorem (Theorem 4.1 , restated) . Let f be a non-negative submodular function on ground set N , and let k\leq n . For any \varepsilon>0 , there exists a set G\subseteq N with |G|=O(k/\varepsilon) such that for every k^{\prime}\leq k , \max_{T\subseteq G,\,|T|\leq k^{\prime}}f(T)\;\geq\;\left(\tfrac{1}{2}-\varepsilon\right)\cdot\mathrm{OPT}_{k^{\prime}}, where \mathrm{OPT}_{k^{\prime}}=\max_{|S|\leq k^{\prime}}f(S) . Moreover, G can be constructed in O(nk/\varepsilon) oracle queries. Proof overview. The proof uses the sequential disjoint greedy (SDG) scheme and proceeds in four steps, all original to this paper. The high-level idea: run greedy many times on disjoint parts of the ground set, find the best run by averaging, then show that this run’s greedy prefix captures at least half the optimal value. Step 1: Averaging. Build \ell disjoint greedy solutions. Because the runs use disjoint elements, their total “damage” to the optimal value is bounded by submodularity (Fact G.1 ). Averaging selects the run that complements OPT best, losing only a (1-1/\ell) factor. Step 2: Partial-greedy domination. The elements of \hat{O}=O\setminus G (the “missed” OPT elements) were available as candidates during the chosen greedy run but were not picked. Since greedy always picks the highest-marginal element, each greedy pick dominates the corresponding missed element. Telescoping gives f(\hat{O}\cup A)\leq 2f(A)-f(\emptyset) : the greedy prefix captures at least half the value of the prefix augmented with the missed elements. Step 3: Submodularity decomposition. The lattice inequality f(X\cup Y)+f(X\cap Y)\leq f(X)+f(Y) , applied to X=\hat{O}\cup A and Y=\dot{O}\cup A , relates the value of O\cup A to the two feasible candidates A and \dot{O}\cup A . Step 4: Feasibility. Both A and \dot{O}\cup A have size at most k^{\prime} and lie in G , so the maximum over them gives the claimed 1/2-\varepsilon containment. The argument uses one standard submodularity fact for disjoint sets, stated for reference: Fact G.1 (Submodularity of disjoint-union marginals) . Let f be non-negative and submodular, and let A_{1},\ldots,A_{\ell} be pairwise disjoint. Then for any set O : \displaystyle\sum_{i=1}^{\ell}f(A_{i}\mid O) \displaystyle\geq f\!\bigl(\textstyle\bigcup_{i}A_{i}\,\big|\,O\bigr), \displaystyle f\!\bigl(\textstyle\bigcup_{i}A_{i}\,\big|\,O\bigr) \displaystyle\leq f\!\bigl(\textstyle\bigcup_{i}A_{i}\cup O\bigr). This follows from repeated application of the diminishing-returns property of submodularity: adding disjoint sets one at a time, each marginal is at least as large as the joint marginal. Proof of Theorem 4.1 . Set \ell=\lceil 1/\varepsilon\rceil . If |N|<\ell k , output G=N ; containment is exact since every k^{\prime} -subset of N is available, and |G|=|N|<\ell k=O(k/\varepsilon) . Otherwise, build \ell disjoint greedy solutions sequentially: G_{1}=\mathrm{greedy}(N,k) , G_{2}=\mathrm{greedy}(N\setminus G_{1},k) , …, G_{\ell}=\mathrm{greedy}(N\setminus\bigcup_{j<\ell}G_{j},k) . Let G=\bigcup_{i=1}^{\ell}G_{i} , so |G|=\ell k . Fix any k^{\prime}\leq k . Write O for an optimal feasible set: |O|\leq k^{\prime} and f(O)=\mathrm{OPT}_{k^{\prime}} . Let b=|O\setminus G| and decompose: \dot{O}=O\cap G,\quad\hat{O}=O\setminus G,\quad|\dot{O}|=|O|-b,\quad|\hat{O}|=b. Step 1 (Averaging). For each i , let A_{i} denote the first b elements of greedy run i . Since A_{i}\subseteq G_{i} and the G_{i} are disjoint, the A_{i} are disjoint. By Fact G.1 applied to the disjoint collection: \sum_{i=1}^{\ell}\bigl[f(O)-f(O\cup A_{i})\bigr]=-\sum_{i=1}^{\ell}f(A_{i}\mid O)\leq-f\!\bigl(\textstyle\bigcup A_{i}\mid O\bigr)=f(O)-f\!\bigl(O\cup\textstyle\bigcup A_{i}\bigr)\leq f(O). By averaging, there exists i^{*} with f(O\cup A_{i^{*}})\geq(1-1/\ell)\,f(O) . Set A=A_{i^{*}} . Step 2 (Partial greedy). Recall A=A_{i^{*}} , the first b elements of greedy run i^{*} (note b\leq k^{\prime}\leq k , so these elements are well-defined). Since \hat{O}\cap G_{j}=\emptyset for every j (by definition of \hat{O}=O\setminus G ), every element of \hat{O} is available as a candidate in greedy run i^{*} . Thus each greedy pick a_{j} satisfies f(a_{j}\mid A_{j-1})\geq f(\hat{o}_{j}\mid A_{j-1}) for some ordering \hat{o}_{1},\ldots,\hat{o}_{b} of \hat{O} (since greedy picks the maximum marginal and \hat{o}_{j} is available). By the telescoping chain and submodularity: \displaystyle f(A)-f(\emptyset) \displaystyle=\sum_{j=1}^{b}f(a_{j}\mid A_{j-1})\geq\sum_{j=1}^{b}f(\hat{o}_{j}\mid A_{j-1})\geq\sum_{j=1}^{b}f(\hat{o}_{j}\mid A) \displaystyle\geq f(\hat{O}\mid A)=f(\hat{O}\cup A)-f(A). (1) Therefore 2f(A)-f(\emptyset)\geq f(\hat{O}\cup A) . Step 3 (Submodularity decomposition). Apply submodularity with X=\hat{O}\cup A and Y=\dot{O}\cup A : f(X\cup Y)+f(X\cap Y)\leq f(X)+f(Y) . Since X\cup Y=O\cup A and X\cap Y=A : f(O\cup A)+f(A)\leq f(\hat{O}\cup A)+f(\dot{O}\cup A). Using ( 1 ): f(\hat{O}\cup A)\leq 2f(A)-f(\emptyset) , so f(O\cup A)\leq f(A)-f(\emptyset)+f(\dot{O}\cup A). (2) Step 4 (Feasibility and conclusion). Both candidates are feasible subsets of G : A\subseteq G_{i^{*}}\subseteq G with |A|=b\leq k^{\prime} ; and \dot{O}\cup A\subseteq G with |\dot{O}\cup A|\leq|\dot{O}|+|A|=|O|\leq k^{\prime} . From ( 2 ) and Step 1: \max\bigl(f(A),\,f(\dot{O}\cup A)\bigr)\geq\frac{f(O\cup A)+f(\emptyset)}{2}\geq\frac{(1-1/\ell)\cdot\mathrm{OPT}_{k^{\prime}}+f(\emptyset)}{2}. Since f(\emptyset)\geq 0 and k^{\prime}\leq k was arbitrary with \ell=\lceil 1/\varepsilon\rceil , the set G achieves containment factor \alpha\geq(1-1/\ell)/2\geq 1/2-\varepsilon simultaneously at every scale k^{\prime}\leq k . ∎ Appendix H Item-Splitting Machinery and Proof of Theorem 4.5 This appendix makes the knapsack extension fully self-contained. Why item splitting is needed. In the cardinality setting, each greedy prefix of length b matches the budget exactly. With knapsack constraints, a density-greedy prefix may overshoot the target budget: the last item added may have cost larger than the remaining budget allows. Item splitting resolves this by conceptually breaking the boundary item into two fragments—one that fits the budget and one that does not—while preserving submodularity of the objective function. The item-splitting construction is due to Feldman and Kuhnle [ 2 ] (Definitions 7.13 and 7.15 there); we restate the pieces needed for Theorem 4.5 and defer the submodularity-preservation proof to [ 2 ] . H.1 The \gamma -split extension Definition H.1 (Gamma-split) . This is the split operation of Feldman and Kuhnle [ 2 ] . Let f\colon 2^{N}\to\mathbb{R}_{\geq 0} be submodular with positive price vector p . For s\in N and \gamma\in(0,1) , the \gamma -split of s produces a new ground set N^{*}=(N\setminus\{s\})\cup\{\sigma_{1},\sigma_{2}\} , prices p^{*}_{\sigma_{1}}=\gamma p_{s} , p^{*}_{\sigma_{2}}=(1-\gamma)p_{s} , p^{*}_{u}=p_{u} otherwise, and function f^{*}(S)\;=\;f(\widehat{S})\;+\;\gamma\cdot f(s\mid\widehat{S})\cdot\mathbb{I}[\sigma_{1}\in S]\;+\;(1-\gamma)\cdot f(s\mid\widehat{S})\cdot\mathbb{I}[\sigma_{2}\in S], where \widehat{S}=S\setminus\{\sigma_{1},\sigma_{2}\} . When S\cap\{\sigma_{1},\sigma_{2}\}=\emptyset , f^{*}(S)=f(S) . When \{\sigma_{1},\sigma_{2}\}\subseteq S , f^{*}(S)=f(\widehat{S}+s) . Lemma H.2 (Split preserves submodularity) . Feldman and Kuhnle [ 2 , Lemma 7.14] prove that the function f^{*} of Definition H.1 is non-negative and submodular on N^{*} . Iterating the split operation finitely many times preserves both properties. Observation H.3 (Density preservation) . This is the density-preservation property from Feldman and Kuhnle [ 2 , Obs. 7.16] . After a \gamma -split of s , for any set S\subseteq N^{*} with \sigma_{1}\notin S resp. \sigma_{2}\notin S , f^{*}(\sigma_{1}\mid S)\;=\;\gamma\cdot f(s\mid\widehat{S}),\qquad f^{*}(\sigma_{2}\mid S)\;=\;(1-\gamma)\cdot f(s\mid\widehat{S}). Together with p^{*}_{\sigma_{i}}=\gamma_{i}p_{s} (with \gamma_{1}=\gamma , \gamma_{2}=1-\gamma ), this gives the density equality f^{*}(\sigma_{i}\mid A_{\sigma_{i}})/p^{*}_{\sigma_{i}}=f(s\mid A_{s})/p_{s} , where A_{s} is the greedy prefix up to s and A_{\sigma_{i}} is its image under the split. Moreover, the equality is stable under iteration: if s itself was produced by a prior \gamma^{\prime} -split of an ancestor \tilde{s} , then f^{*}(s\mid A_{s})/p^{*}_{s}=f^{**}(\tilde{s}\mid A_{\tilde{s}})/p^{**}_{\tilde{s}} by the same identity applied to that earlier split, and inductively every fragment u in the descendants of \tilde{s} satisfies f^{*}(u\mid A_{u})/p^{*}_{u}=f(\tilde{s}\mid A_{\tilde{s}})/p_{\tilde{s}} , i.e. the density class of an element is preserved across any finite sequence of splits applied to it or to disjoint elements of the prefix. H.2 The \theta -construction In this subsection U and V live in the current split ground set. We write p^{*}_{x} for the cost of a split-ground-set element x ; for an unsplit original item, p^{*}_{x}=p_{x} . Given finite sets U,V with c(U)\leq c(V) and a greedy ordering on V , the following iterative procedure builds a mapping \theta\colon U\to V (after possibly splitting some elements of U ) maintaining the invariant \sum_{u\in\theta^{-1}(a)}p^{*}_{u}\leq p^{*}_{a} for every a\in V . Definition H.4 (Iterative theta-construction) . This is the iterative construction of Feldman and Kuhnle [ 2 , Def. 7.15] . Initially \theta is undefined on U . Repeat: if \theta is defined on all of U , terminate. Otherwise let u be the last element of U for which \theta is undefined, and a the last element of V for which \sum_{u^{\prime}\in\theta^{-1}(a)}p^{*}_{u^{\prime}}
\sum_{a\in V}\sum_{u^{\prime}\in\theta^{-1}(a)}p^{*}_{u^{\prime}}
, so a non-tight
a
exists and
the construction never blocks. After all splits,
c(U)
summed over
the post-split elements still equals the pre-split
c(U)
.
Lemma H.5
(Density-domination lemma)
.
This lemma is adapted from the density-preservation observation of
Feldman and Kuhnle
[
2
, Obs. 7.16]
.
Let
\theta\colon U\to V
be the mapping of
Definition
H.4
, where
V
is a density-greedy-ordered
prefix of a greedy run, possibly with its last item replaced by an included
boundary fragment. Assume every original element from which an element of
U
descends was a density-greedy candidate at every step of that run.
Then for every
a\in V
and every
u\in\theta^{-1}(a)
,
\frac{f^{*}(u\mid A_{a})}{p^{*}_{u}}\;\leq\;\frac{f^{*}(a\mid A_{a})}{p^{*}_{a}}.
Consequently,
\sum_{u\in\theta^{-1}(a)}f^{*}(u\mid A_{a})\;\leq\;\frac{f^{*}(a\mid A_{a})}{p^{*}_{a}}\sum_{u\in\theta^{-1}(a)}p^{*}_{u}\;\leq\;f^{*}(a\mid A_{a}),
where
A_{a}
is the greedy prefix strictly preceding
a
and
the last inequality uses the invariant
\sum_{u\in\theta^{-1}(a)}p^{*}_{u}\leq p^{*}_{a}
.
Proof idea.
Let
s(u)
be the original item from which
u
descends, and let
b(a)
be
the original greedy item from which
a
descends (so
b(a)=a
if
a
is not
a boundary fragment). Observation
H.3
gives
\frac{f^{*}(u\mid A_{a})}{p^{*}_{u}}=\frac{f(s(u)\mid A_{a})}{p_{s(u)}},\qquad\frac{f^{*}(a\mid A_{a})}{p^{*}_{a}}=\frac{f(b(a)\mid A_{a})}{p_{b(a)}}.
The original item
s(u)
was a density-greedy candidate when
b(a)
was
selected from prefix
A_{a}
, hence its density was no larger than the density
of
b(a)
. This gives the individual density bound. Multiplying it by
p^{*}_{u}
and summing over
u\in\theta^{-1}(a)
gives the displayed
consequence; no sum of densities is compared directly to a single density.
∎
H.3
Full proof of Theorem
4.5
Theorem
(Theorem
4.5
, restated)
.
For any
\varepsilon\in(0,1/2)
, sequential disjoint density-greedy with
\ell=\lceil 1/\varepsilon\rceil
runs produces a set
P\subseteq N
with
c(P)\leq 3\ell B=O(B/\varepsilon)
such that for every
B^{\prime}\in(0,B]
there exists
Q\subseteq P
with
c(Q)\;\leq\;B^{\prime},\qquad f(Q)\;\geq\;\left(\tfrac{1}{2}-\varepsilon\right)\mathrm{OPT}_{B^{\prime}}\;-\;\Delta_{B^{\prime}},
where
\Delta_{B^{\prime}}\geq 0
is a boundary-fragment loss that arises when the
density-greedy prefix crosses the budget threshold mid-item. When no item
is split,
\Delta_{B^{\prime}}=0
.
Total query complexity:
O(n^{2}/\varepsilon)
.
Proof overview.
This is the most technical proof in the paper, and the reader may wish to
first read the simpler cardinality proof
(Theorem
4.1
, Appendix
G
)
for the core ideas.
The main complication beyond cardinality is that density-greedy prefixes may
not align cleanly with a target budget: the last item added may overshoot,
requiring the item to be “split” into a used and unused fragment.
The item-splitting machinery of Feldman &
Kuhnle
[
2
]
(stated above) handles this by creating
a new ground set where the split item is replaced by two fragments whose
costs sum to the original.
The proof then proceeds in five steps:
Step 1: Boundary split (imported machinery).
For each density-greedy run, identify the prefix whose total cost equals the
residual budget
\beta
, splitting the boundary item if needed via
Definition
H.1
.
Split-submodularity (Lemma
H.2
) ensures the
resulting function
f^{*}
is still submodular.
Step 2: Averaging (original, analogous to the cardinality case).
The disjoint-collection argument from Fact
G.1
, now
applied to the split function
f^{*}
, identifies the best run
i^{\star}
with
f^{*}(O^{\uparrow}\cup A)\geq(1-1/\ell)f(O)
.
Step 3: Density domination (imported+original).
Apply the
\theta
-construction (Definition
H.4
) to map
\hat{O}
into the greedy prefix
A
.
The density-domination lemma (Lemma
H.5
, adapted
from
[
2
]
) then yields
f^{*}(\hat{O}^{\uparrow}\cup A)\leq 2f^{*}(A)-f(\emptyset)
.
Step 4: Submodular decomposition (original).
Apply the lattice inequality
f^{*}(X\cup Y)+f^{*}(X\cap Y)\leq f^{*}(X)+f^{*}(Y)
to relate
f^{*}(O^{\uparrow}\cup A)
to the two candidates.
Step 5: Feasible real subset (original).
Convert the split-function guarantee back to a real-set guarantee, paying the
boundary-fragment loss
\Delta_{B^{\prime}}
.
Proof of Theorem
4.5
.
Fix
\varepsilon\in(0,1/2)
,
\ell=\lceil 1/\varepsilon\rceil
,
and
B^{\prime}\in(0,B]
. Let
O
achieve
\mathrm{OPT}_{B^{\prime}}
; set
\hat{O}=O\setminus P
,
\dot{O}=O\cap P
,
\beta=c(\hat{O})\leq B^{\prime}
.
If
\beta=0
, then
O\subseteq P
, so taking
Q=O
proves the theorem.
Assume below that
\beta>0
.
Step 1 (Budget-specific prefix and boundary split).
For each run
i\in[\ell]
, order
A_{i}=\{a^{(i)}_{1},\ldots,a^{(i)}_{m_{i}}\}
by density-greedy selection time. Let
j_{i}
be the first
index for which
\sum_{r\leq j_{i}}p_{a^{(i)}_{r}}\;\geq\;\beta.
Since
c(A_{i})\geq 2B\geq 2\beta
, such
j_{i}
exists and
\sum_{r