Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions Yixin Chen, Alan Kuhnle Abstract Submodular functions—functions exhibiting diminishing returns—are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight 63 % 63\% approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend curvature —a parameter measuring how far a function deviates from linearity—to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for any submodular function, including those taking negative values—the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime 1 ≤ c g < 2.2 1\leq c_{g}<2.2 , the bound strictly beats the best known uniform ratio of 0.401 0.401 (for non-negative f f ), and it recovers the classical ( 1 − e − c g ) / c g (1-e^{-c_{g}})/c_{g} guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory. 1 Introduction Submodular optimization in machine learning. Sensor placement for environmental monitoring [ 13 ] , data summarization for information retrieval [ 16 ] , feature selection for model training [ 12 ] , and Bayesian experimental design [ 11 ] share a common mathematical structure: their objective functions exhibit diminishing returns —adding an element to a smaller collection yields at least as much benefit as adding it to a larger one. Functions with this property are called submodular , and the canonical optimization task is to select a subset of at most k items maximizing a submodular objective f . When f is monotone (more items never hurt) and non-negative, the simple greedy algorithm—repeatedly adding the element with the largest marginal gain—achieves a tight (1-1/e)\approx 0.632 approximation [ 18 ] . The greedy guarantee has made submodular optimization a practical workhorse in these settings. When objectives go negative. In practice, each of these applications involves costs. Deploying a sensor costs money; including a document incurs retrieval overhead; each training example or experiment requires resources. The natural formulation subtracts a modular cost \ell from a monotone submodular benefit g , giving an objective f=g-\ell that is still submodular but takes negative values whenever costs exceed benefits—a sensor whose installation cost outweighs its information gain, a feature whose \ell_{1} penalty outweighs its mutual information, or an experiment whose acquisition cost dominates its value [ 13 , 12 , 11 ] . This is the routine regime of cost-benefit trade-offs. For non-monotone but non-negative objectives, a decade of work has driven the best approximation from 1/e [ 3 ] to 0.401 [ 4 ] , against a hardness ceiling of 0.478 [ 20 , 21 ] . But every result in this line requires f(S)\geq 0 for every S : the correlation gap argument [ 5 ] that connects the multilinear relaxation to the discrete problem collapses when f takes negative values, providing no approximation guarantee whatsoever . Two partial solutions and their limitations. Existing work addresses negativity or non-monotonicity, through separate frameworks; we extend a single classical concept to handle both simultaneously. 11 initiated a line of work that decomposes f=g-\ell and proves that a distorted greedy achieves \mathbb{E}[f(S)]\geq(1-1/e)\,g(\mathrm{OPT})-\ell(\mathrm{OPT}) , an additive guarantee subsequently extended to several settings [ 12 , 15 , 2 ] . The additive guarantee mixes the incommensurable quantities g(\mathrm{OPT}) and \ell(\mathrm{OPT}) . Converting it to a multiplicative ratio on f itself gives 1-1/(e(1-\rho)) where \rho=\ell(\mathrm{OPT})/g(\mathrm{OPT}) , which becomes vacuous once the cost ratio exceeds \rho\geq 1-1/e\approx 0.632 —a sharp threshold, not a graceful degradation—and requires explicit access to g and \ell separately, while many objectives are given only as a value oracle. Separately, 17 developed partial monotonicity as a structural parameter for non-monotone submodular maximization, but this addresses non-monotonicity alone—it does not handle objectives that go negative, nor does it connect to the classical structural theory that made the greedy guarantee instance-dependent. Curvature: from monotone to general. The concept we extend is curvature [ 7 ] , a parameter c\in[0,1] for monotone submodular functions that measures how far f deviates from linearity. When c=0 the function is linear (modular) and greedy is exact; as c grows toward 1 , diminishing returns become more pronounced and the greedy guarantee degrades smoothly from 1 to 1-1/e via the bound (1-e^{-c})/c . 22 proved this bound is tight under matroid constraints, establishing curvature as the canonical instance-dependent refinement for monotone submodular maximization. The classical definition, however, diverges when marginals go negative, and the associated guarantee says nothing. This leads to a natural question: can curvature be extended to non-monotone, and possibly negative, submodular functions in a way that yields multiplicative approximation guarantees? Figure 1 : The curvature spectrum. (a) Illustrative submodular functions h(|S|) at different curvatures. Modular ( c=0 ): linear growth. Low curvature ( c=0.5 ): mild diminishing returns. Monotone boundary ( c=1 ): the function flattens but remains non-decreasing. Symmetric ( c=2 ): the function peaks at |S|=n/2 and returns to zero, as in max-cut. Beyond ( c=3 ): the function goes negative for large sets. (b) Approximation guarantees as a function of the relevant curvature parameter c . The blue region ( c\leq 1 ) recovers classical monotone results [ 7 , 22 ] . The green region ( 10 , as any element with f\left(e\right)\leq 0 can be removed without affecting the optimum. 1 1 1 Normalization f\left(\emptyset\right)=0 is standard for monotone maximization but typically avoided for non-monotone functions, as it may cause f to take negative values. 2.1 Curvature: Definition and Basic Properties Our generalization replaces the classical element-wise ratio with a set-wise comparison: how much does the value of Y\setminus X degrade when added in the context of X ? This avoids the element-level marginals that diverge for non-monotone functions. Since the minimum in Definition 1 is taken over all pairs with f\left(Y\setminus X\right)-f\left(\emptyset\right)>0 , and submodularity ensures f\left(X\cup Y\right)-f\left(X\right)\leq f\left(Y\setminus X\right)-f\left(\emptyset\right) , the curvature satisfies c_{f}\geq 0 for every submodular f . Definition 1 (Curvature) . The curvature c_{f}\in[0,\infty) of a submodular function f:2^{\mathcal{N}}\to\mathbb{R} is defined as c_{f}=1-\min_{\begin{subarray}{c}X,Y\subseteq\mathcal{N}\\ f\left(Y\setminus X\right)-f\left(\emptyset\right)>0\end{subarray}}\frac{f\left(X\cup Y\right)-f\left(X\right)}{f\left(Y\setminus X\right)-f\left(\emptyset\right)}. Equivalently, c_{f} is the minimum value such that, for all X,Y\subseteq\mathcal{N} with f\left(Y\setminus X\right)-f\left(\emptyset\right)>0 : f\left(X\cup Y\right)-f\left(X\right)\geq(1-c_{f})\bigl(f\left(Y\setminus X\right)-f\left(\emptyset\right)\bigr). (1) When f\left(\emptyset\right)=0 (as we assume throughout), the -f\left(\emptyset\right) terms vanish. When c_{f}\leq 1 , this says adding Y\setminus X to X remains non-negative and captures at least a (1-c_{f}) fraction of the standalone value of Y\setminus X . When c_{f}>1 , the union can degrade value: adding Y\setminus X to X may reduce the function value by up to (c_{f}-1)\,f\left(Y\setminus X\right) . Submodularity also gives the companion upper bound f\left(X\cup Y\right)-f\left(X\right)\leq f\left(Y\setminus X\right) . Example 1 . For cardinality-constrained MaxCut, c_{f}=2 (Proposition 3 ). The global curvature c_{f} may be much larger than what the algorithm actually encounters along its trajectory—a worst-case set pair may never arise during execution. To capture this, we define a tighter, trajectory-specific variant. Definition 2 (Greedy curvature) . Fix a cardinality constraint k . Let \mathcal{O}=\argmax_{|S|\leq k}f\left(S\right) be the set of optimal solutions and let A_{0},A_{1},\ldots,A_{k} be the active sets generated by greedy with pruning (Algorithm 1 ), repeating the terminal set if the algorithm stops early. These active sets are not required to be nested: pruning may delete elements chosen in earlier iterations. The greedy curvature is c_{g}\;=\;1-\min_{O^{*}\in\mathcal{O}}\;\min_{i:\,f\left(A_{i}\setminus O^{*}\right)-f\left(\emptyset\right)>0}\frac{f\left(O^{*}\cup A_{i}\right)-f\left(O^{*}\right)}{f\left(A_{i}\setminus O^{*}\right)-f\left(\emptyset\right)}. By construction, c_{g}\leq c_{f} , since the minimization is over the trajectory pairs (O^{*},A_{i}) , a subset of the pairs allowed in Definition 1 . Proposition 1 (Monotonicity characterization) . A submodular function f with f\left(e\right)>0 for all e\in\mathcal{N} is monotone if and only if c_{f}\leq 1 . This result means curvature cleanly partitions the function space: c_{f}\leq 1 is precisely the monotone regime, so functions with c_{f}>1 are necessarily non-monotone. The curvature parameter thus simultaneously measures distance from linearity and distance from monotonicity. See Appendix J for the proof. Proposition 2 (Classical equivalence) . For monotone submodular f , the curvature c_{f} equals the total curvature \alpha of 7 : 1-\alpha=\min_{e:\Delta\left(e|\emptyset\right)>0}\Delta\left(e|\mathcal{N}\setminus e\right)/\Delta\left(e|\emptyset\right) . This equivalence ensures backward compatibility: every result proved using the CC parameter \alpha transfers directly to c_{f} for monotone functions, while our generalization extends the same quantity beyond the monotone boundary. See Appendix J for the proof. Notation. Throughout, c_{f} denotes the set-function curvature (Definition 1 ), a global quantity; c_{g} denotes the greedy curvature (Definition 2 ), restricted to the greedy trajectory and satisfying c_{g}\leq c_{f} . The multilinear analogues c_{F} and c_{g}^{F} (stated in Section 3 ; formally defined in Appendix G ) extend these to continuous relaxations. When comparing to the classical Conforti–Cornuéjols literature, \alpha and \alpha_{g} refer to the CC curvature of a monotone submodular function, where \alpha=c_{f} by Proposition 2 . 2.2 Discrete Greedy with Pruning The cleanest algorithmic setting for the set-level curvature is the cardinality-constrained discrete greedy algorithm (Algorithm 1 ). Here the curvature inequality can be applied directly to sets along the greedy trajectory, without first passing through a relaxation. The multilinear obstruction discussed below motivates the trajectory machinery needed for the continuous lift in Section 3 . The key algorithmic device in the discrete result is a pruning loop : after each greedy addition, any element whose marginal to the rest of the current set has turned non-positive is removed. The pruning loop supplies the local positivity needed by the curvature recurrence: every nonempty subset of the active set has positive value, and f is monotone within the active set (Remark 1 ). Theorem 1 (Greedy guarantee) . Let f be submodular with greedy curvature c_{g} (Definition 2 ), and let O^{*}\in\argmax_{|S|\leq k}f\left(S\right) . Put \bar{c}_{g}=\max\{1,c_{g}\} . Then \textsc{Greedy}(f,k) (Algorithm 1 , Appendix B ) returns A_{k} with f\left(A_{k}\right)\geq\frac{1-e^{-\bar{c}_{g}}}{\bar{c}_{g}}\,f\left(O^{*}\right) . If f is monotone, the classical Conforti–Cornuéjols analysis gives the sharper \frac{1-e^{-c_{g}}}{c_{g}} bound when c_{g}<1 . Proof. Write A_{0},A_{1},\ldots,A_{k} for the active sets produced by the algorithm. Let \bar{c}_{g}=\max\{1,c_{g}\} . Since \bar{c}_{g}\geq c_{g} , the curvature inequality is valid with \bar{c}_{g} in place of c_{g} . \displaystyle f\left(A_{i+1}\right)-f\left(A_{i}\right) \displaystyle\geq f\left(A_{i+1}^{\prime}\right)-f\left(A_{i}\right) (pruning can only increase) \displaystyle\geq\frac{1}{k}\sum_{o\in O^{*}\setminus A_{i}}\Delta\left(o|A_{i}\right) (greedy selection) \displaystyle\geq\frac{1}{k}[f\left(O^{*}\cup A_{i}\right)-f\left(A_{i}\right)] (submodularity) \displaystyle\geq\frac{1}{k}[f\left(O^{*}\right)+(1-\bar{c}_{g})f\left(A_{i}\setminus O^{*}\right)-f\left(A_{i}\right)] (curvature) \displaystyle\geq\frac{1}{k}[f\left(O^{*}\right)-\bar{c}_{g}\,f\left(A_{i}\right)]. ( \bar{c}_{g}\geq 1 , local monotonicity on A_{i} ) The curvature step uses Definition 2 at the pair (O^{*},A_{i}) along the greedy trajectory; only the trajectory-restricted c_{g} is needed. If A_{i}\setminus O^{*} is nonempty, Remark 1 gives f\left(A_{i}\setminus O^{*}\right)>0 , so the pair is admissible in Definition 2 . If A_{i}\setminus O^{*}=\emptyset , the same display holds with the curvature term equal to zero. The last inequality uses f\left(A_{i}\setminus O^{*}\right)\leq f\left(A_{i}\right) , which follows from the local monotonicity of f on the pruned active set (Remark 1 ); this is the step that requires using a curvature parameter at least 1 . If \bar{c}_{g}\leq k , the recurrence f\left(A_{i+1}\right)\geq f\left(O^{*}\right)/k+(1-\bar{c}_{g}/k)f\left(A_{i}\right) solves to f\left(A_{k}\right)\geq\frac{f\left(O^{*}\right)}{\bar{c}_{g}}(1-(1-\bar{c}_{g}/k)^{k})\geq\frac{f\left(O^{*}\right)}{\bar{c}_{g}}(1-e^{-\bar{c}_{g}}) . If \bar{c}_{g}>k , the first greedy step already gives f\left(A_{1}\right)\geq f\left(O^{*}\right)/k>f\left(O^{*}\right)/\bar{c}_{g} , and subsequent accepted additions and prunings do not decrease the value; this is stronger than the displayed bound. ∎ Remark 1 (The pruning loop) . The pruning loop removes elements with non-positive marginal contribution. By submodularity, for any nonempty S\subseteq A_{i} the telescoping sum f\left(S\right)=\sum_{j=1}^{|S|}\Delta\left(s_{j}|\{s_{1},\ldots,s_{j-1}\}\right)\geq\sum_{j=1}^{|S|}\Delta\left(s_{j}|A_{i}\setminus s_{j}\right)>0 , since every remaining element has strictly positive marginal to the rest. The same argument, applied to A_{i}\setminus S and telescoping from S up to A_{i} , gives f\left(S\right)\leq f\left(A_{i}\right) for every S\subseteq A_{i} . Hence every nonempty subset of A_{i} has positive value, and f is monotone inside the active set. These are exactly the local properties used in the proof above. The algorithm does not need to know c_{g} . Algorithm 1 runs in O(nk) oracle queries. Lazy (priority-queue) greedy can be used between pruning events, but after pruning shrinks the active set the cached marginal upper bounds must be rebuilt or revalidated. With that caveat, the practical query count is often close to O(n+k\log n) . Whether a near-linear-time threshold greedy variant exists is an open question (see Section 5 ). Toward the multilinear extension. A natural question is whether our set-level curvature extends to the multilinear extension F of f . Such an extension would provide one route to lifting the greedy guarantee from cardinality constraints to general combinatorial constraints—matroids, knapsacks, and their intersections—via continuous relaxation methods. For strictly positive functions ( f\left(S\right)>0 for all nonempty S ), this works: the multilinear curvature c_{F} equals the discrete curvature c_{f} (Theorem 3 (a), Appendix G ). However, there is an obstruction. When f takes any negative value, c_{F}=\infty (Proposition 7 , Appendix G ): mass can be concentrated on an inclusion-minimal negative set, driving the curvature denominator to zero. Section 3 resolves this via DMCG-P, which restricts curvature to the algorithm’s trajectory and uses pruning to maintain a positive-slope invariant. 3 Beyond Cardinality: the DMCG-P Guarantee The discrete greedy result (Theorem 1 ) handles cardinality constraints. For general combinatorial constraints—matroids, knapsack, and their intersections—a standard approach is to optimize the multilinear extension F over a relaxation of the feasible family. The classical continuous-greedy analysis requires bounded global curvature c_{F} , but for negative-valued f this diverges (Proposition 7 , Appendix G ). We resolve this via DMCG-P (Discretized Measured Continuous Greedy with Pruning; Algorithm 2 ), which restricts curvature to the algorithm’s trajectory. The algorithmic ideas mirror the discrete proof but in fractional form. Each step chooses an integral feasible direction by exact linear optimization over the current multilinear slopes, takes a small \delta=1/T step, and then zeroes coordinates whose slopes have become non-positive. Discretization lets the continuous trajectory be analyzed through set-level greedy/pruning increments, while the positive-slope pruning invariant removes the immediate zero-slope obstruction that makes the global curvature c_{F} unusable. The theorem below still states finite trajectory curvature as a hypothesis; in the applications section, decomposable objectives give one concrete certificate for that hypothesis. Theorem 2 (DMCG-P guarantee; see Appendix G ) . Let \mathcal{I}\subseteq 2^{\mathcal{N}} be downward-closed with \mathcal{P}=\operatorname{conv}\{\mathbf{1}_{S}:S\in\mathcal{I}\} , and assume exact linear optimization over \mathcal{I} . For any submodular f (no monotonicity or non-negativity required) with trajectory-restricted fractional curvature c_{g}^{F}<\infty and \bar{c}_{g}^{F}\triangleq\max\{1,c_{g}^{F}\} , DMCG-P with T steps (step size \delta=1/T , with \delta\bar{c}_{g}^{F}\leq 1 ) returns \tilde{S}_{T}\in\mathcal{P} satisfying F(\tilde{S}_{T})\;\geq\;\frac{1-e^{-\bar{c}_{g}^{F}}}{\bar{c}_{g}^{F}}\,f\left(O^{*}\right)\;-\;O\!\left(\frac{n(n{-}1)\,C_{F}}{T}\right), where n=|\mathcal{N}| , and C_{F}=\max_{j\neq\ell,\,\mathbf{x}\in[0,1]^{\mathcal{N}}}|\partial_{j\ell}F(\mathbf{x})| is the smoothness constant, with O^{*}\in\argmax_{S\in\mathcal{I}}f(S) . The step count T is independent of the constraint; choosing T large enough makes the error negligible at the cost of O(Tn) oracle calls. The finite-curvature hypothesis uses the positive-denominator convention in Definition 4 ; pruning supplies the slope invariant used in the proof, but a certificate is needed to verify finiteness in a concrete instance. In the application section below, decomposable objectives f=g-\ell provide one concrete way to certify the finite-curvature hypothesis: the pruned trajectory yields an OPT-free ratio \hat{r}_{F}<1 with c_{g}^{F}\leq\alpha_{g}/(1-\hat{r}_{F}) (Proposition 9 ). For non-negative non-monotone f , a damped weighted variant (wDMCG-P; Algorithm 3 ) recovers the e^{-1} guarantee (Theorem 5 ). Table 5 in Appendix G summarizes the full landscape. With the general guarantee in hand, we now apply it to three concrete function classes, each compared to the best previously available tool. 4 Applications and Experiments Each application class answers a different question about the curvature framework. Symmetric submodular functions test whether curvature subsumes specialized structural results: with c_{f}=2 , the guarantee recovers the known 0.432 ratio for graph cuts and clustering [ 23 ] (Section 4.1 ). Decomposable objectives f=g-\ell test whether curvature can replace additive bounds: closed-form certificates yield per-instance multiplicative guarantees that improve on the HFWK additive bound at moderate cost ratios (Section 4.2 ). GCLin diversity objectives test practical relevance: the relevance-minus-redundancy family introduced for summarization by 14 has curvature at most 2\lambda under uniform query weights ( \lambda\leq 1 ), giving a \lambda -dependent multiplicative guarantee that remains positive where the partial-monotonicity parameter of 17 has already vanished (Section 4.3 ). The decomposable experiments use greedy+pruning (Algorithm 1 ) with distorted greedy [ 11 ] as a baseline; the MaxCut experiment adds standard greedy and random greedy [ 3 ] ; the GCLin experiment uses greedy with best-prefix selection. Full details are in Appendix E . 4.1 Symmetric Submodular Functions Symmetric submodular functions—those satisfying f(S)=f(\mathcal{N}\setminus S) —are a central class in combinatorial optimization, encompassing graph cuts, hypergraph partitioning, and clustering objectives [ 23 , 10 ] . Any normalized symmetric submodular function is automatically non-negative: submodularity applied to S and \mathcal{N}\setminus S gives 2f(S)=f(S)+f(\mathcal{N}\setminus S)\geq f(\mathcal{N})+f(\emptyset)=0 . For general non-monotone maximization, the uniform guarantee is 1/e ; symmetric objectives are one structured setting where specialized algorithms exceed it [ 10 , 24 ] , but curvature provides a structural explanation for why greedy+pruning already exceeds this barrier. Proposition 3 (Symmetric functions) . Let f be normalized, symmetric ( f\left(S\right)=f\left(\mathcal{N}\setminus S\right) ), and submodular, and suppose f has a positive singleton. Then f is non-negative and c_{f}=2 . Proof idea. Symmetry forces f\left(X\cup Y\right)-f\left(X\right)\geq-f\left(Y\setminus X\right) (ratio \geq-1 , so c_{f}\leq 2 ); choosing X=\mathcal{N}\setminus Y gives f\left(\mathcal{N}\right)-f\left(Y\right)=-f\left(Y\right) (ratio =-1 , so c_{f}\geq 2 ). See Appendix J . Since c_{g}\leq c_{f} , Theorem 1 gives f(A_{k})\;\geq\;\frac{1-e^{-2}}{2}\,f(O^{*})\;\approx\;0.432\,f(O^{*}) under a cardinality constraint. While specialized algorithms also achieve above- 1/e guarantees for this class [ 10 , 24 ] , curvature provides a structural lens : the guarantee comes from deterministic greedy+pruning via a single parameter c_{f} , without using symmetry at runtime, and the same framework seamlessly covers non-symmetric and negative-valued objectives. This is also where the comparison with partial monotonicity is clearest: for cut-type symmetric instances the monotonicity ratio can be zero, while the curvature bound remains strictly above 1/e . Appendix F.5 validates this on cardinality-constrained MaxCut instances, where greedy+pruning consistently improves on standard greedy at large budget ratios. Symmetric functions demonstrate that curvature subsumes specialized structural results; we now turn to a class where it improves on the only available prior guarantee. 4.2 Decomposable Objectives: the Curvature Certificate Cost-penalized objectives f=g-\ell arise whenever a monotone benefit g competes with a modular cost \ell : sensor placement with deployment costs [ 11 ] , regularized feature selection [ 12 ] , and budget-constrained experimental design are canonical examples. 11 gave the only prior guarantee for this class: an additive bound (1-1/e)\,g(O^{*})-\ell(O^{*}) that becomes vacuous at moderate cost ratios. Curvature provides multiplicative certificates. Writing g with CC curvature \alpha_{g} and \ell modular (so F=G-L with L linear in the multilinear extension), the pruned trajectory itself gives an OPT-free bound on the curvature encountered by the algorithm; neither statement requires non-negativity of f . Proposition 4 (OPT-free decomposable trajectory certificate) . Let f=g-\ell where g:2^{\mathcal{N}}\to\mathbb{R}_{\geq 0} is monotone submodular with Conforti–Cornuéjols curvature \alpha_{g} , and \ell:2^{\mathcal{N}}\to\mathbb{R}_{\geq 0} is modular. Let A_{0},A_{1},\ldots be the active-set trajectory of greedy with pruning, and define \hat{r}\;=\;\max_{i}\max_{e\in A_{i}}\frac{\ell(e)}{\Delta_{g}(e\mid A_{i}\setminus\{e\})}, with value 0 if all active sets are empty. Then \hat{r}<1 and c_{g}\leq\alpha_{g}/(1-\hat{r}) . The denominator is observable after the run. Moreover, pruning makes it valid: every active element has positive f -marginal to the rest of the current active set, so \Delta_{g}(e\mid A_{i}\setminus\{e\})>\ell(e) . The proof in Appendix D shows that this elementwise control lifts to every set difference A_{i}\setminus O^{*} , avoiding any need to know the optimal solution. A sharper OPT-aware ratio is stated in Appendix J . A fractional analogue for DMCG-P trajectories, giving c_{g}^{F}\leq\alpha_{g}/(1-\hat{r}_{F}) via the pruning invariant and DR-submodularity, is proved in Appendix H (Proposition 9 ). In the dominance regime g\geq(1+1/\delta)\ell [ 12 ] , we get c_{g}\leq(1+\delta)\alpha_{g} and the curvature guarantee dominates the HFWK additive bound for all \delta>0 ; HFWK becomes vacuous at \delta\geq e-1\approx 1.72 . When f takes negative values (dominance fails), HFWK is inapplicable, while the trajectory certificates still yield the \bar{c}_{g} -curvature bound via Theorem 1 . They are per-instance: after running the algorithm, one computes the removal-marginal ratios along the pruned trajectory and reports the resulting bound. Experimental validation (small instances). Small instances ( n=20 , k=5 , 10 seeds) with exact OPT validate the curvature framework on three decomposable objectives: Bayesian experimental design ( \alpha_{g}=0.667 ), coverage ( \alpha_{g}=1 ), and feature selection ( \alpha_{g}\approx 0.79 ). Table 1 : Tier 1 (small instances, exact OPT) results: n=20 , k=5 . GP = greedy+pruning, DG = distorted greedy. Curv. guar. is (1-e^{-\bar{c}_{g}})/\bar{c}_{g} using the empirical c_{g} . Cert. guar. is (1-e^{-\bar{\hat{c}}_{g}})/\bar{\hat{c}}_{g} , where \hat{c}_{g}=\alpha_{g}/(1-\hat{r}) is the OPT-free removal-marginal certificate (Proposition 4 ). Under additional assumptions, a tighter certificate is available (Appendix D ). Values are means over 10 seeds. Application \rho GP ratio DG ratio c_{g} Curv. guar. Cert. guar. HFWK Exp. Design 0.09 1.00 1.00 0.13 0.95 0.63 0.60 0.29 1.00 1.00 0.18 0.93 0.61 0.49 0.56 0.98 0.87 0.76 0.74 0.38 0.17 0.76 0.94 0.60 1.61 0.58 0.16 -0.56 Coverage 0.08 0.98 0.98 0.68 0.75 0.58 0.60 0.31 0.94 0.94 1.17 0.60 0.27 0.46 0.50 0.89 0.89 1.41 0.58 0.14 0.27 0.68 0.84 0.78 2.49 0.37 0.11 -0.14 Feature Sel. 0.11 1.00 1.00 0.00 1.00 0.63 0.59 0.39 1.00 1.00 0.00 1.00 0.48 0.40 0.57 1.00 0.91 0.00 1.00 0.26 0.10 0.77 1.00 0.90 0.00 1.00 0.16 -2.01 Table 1 summarizes. Greedy+pruning achieves empirical ratios \geq 0.84 even at high cost levels, substantially outperforming distorted greedy. The curvature guarantee is conservative—at c_{g}\approx 1.6 the guarantee is 58\% against an observed ratio of 94\% . The OPT-free certificate (Proposition 4 ) provides a formal guarantee computable from the pruned trajectory alone, without the small-penalty condition required by the singleton approach; it remains valid even for coverage ( \alpha_{g}=1 ). The feature-selection tier is a near-modular sanity check: the \ell_{1} -regularized mutual information is nearly linear on these small instances, giving c_{g}=0 along the tested trajectories. Experimental design and coverage provide the main diminishing-returns stress tests. Full cost-sweep curves and curvature-vs-ratio scatter plots appear in Appendix F . Moderate-scale instances. At moderate scales ( n up to 300 ), exact OPT is intractable. Trajectory-based curvature diagnostics stay positive at every cost level, while HFWK becomes vacuous at moderate costs (Appendix F , Table 2 and Figure 5 ). 4.3 GCLin Diversity Objective Graph-cut-based objectives are a workhorse for document summarization and information retrieval. 14 showed that the relevance–redundancy tradeoff—each selected passage adds coverage of source material but also redundancy with other selections—is naturally captured by this family. The graph-cut-linear (GCLin) objective f\left(S\right)=R(S)-\lambda D(S) , where R(S)=\sum_{i\in\mathcal{N}}\sum_{j\in S}s_{i,j} rewards relevance and D(S)=\sum_{\begin{subarray}{c}i,j\in S\\ i\neq j\end{subarray}}s_{i,j} penalizes redundancy [ 14 ] , instantiates this directly. LLM context selection—choosing which retrieved passages to include in a prompt—poses the same structural problem: each passage adds relevant evidence but also redundancy, and the context budget imposes a cardinality constraint. Our experiments on Multi-News (below) show that mean trajectory curvature follows the uniform-query reference curve 2\lambda , showing the redundancy penalty meaningfully changes the curvature profile. Proposition 5 . Suppose the GCLin diversity-relevance objective has symmetric non-negative similarities, uniform query weights ( w_{i}=1 ), and 0\leq\lambda\leq 1 . Then c_{f}\leq 2\lambda . Figure 2 (a) compares the resulting uniform-query curvature guarantee (1-e^{-2\lambda})/(2\lambda) for \lambda\leq 1 with the partial-monotonicity-style guarantee of 17 . Partial monotonicity measures value loss under additions. Curvature measures diminishing returns along the same tradeoff. For GCLin, the partial-monotonicity bound vanishes by \lambda=1 , while the uniform-query curvature bound remains positive at that boundary. This is a relevant separation for diversity-heavy passage selection. For \lambda\leq 1/2 , f is monotone and both the discrete and DMCG-P guarantees give (1-e^{-2\lambda})/(2\lambda) . See Appendix J for the proof. Curvature sweep on Multi-News passage selection. We vary curvature via \lambda on Multi-News [ 8 ] : for 100 validation examples ( n=200 , k=10 , TF-IDF embeddings), greedy selects passages under \text{GCLin}_{\lambda} for \lambda\in\{0.1,0.25,0.5,0.75,1.0,1.5\} and a local openai/gpt-oss-120b endpoint summarizes them (prompt and decoding details in Appendix E ). Figure 2 shows two key findings: (b) the mean trajectory-curvature proxy \hat{c}_{\text{traj}} stays below the uniform-query reference bound 2\lambda for \lambda\leq 1 ; individual instances occasionally exceed it because the TF-IDF query weights are non-uniform (the proposition assumes uniform weights). \lambda=1.5 is reported only as an empirical high-redundancy diagnostic; (c) the resulting clipped trajectory guarantee is tighter than the uniform-query reference curve for \lambda\leq 1 and remains informative as a diagnostic at \lambda=1.5 . (a) (b) (c) Figure 2 : GCLin diversity objective: theoretical and empirical analysis. (a) Uniform-query curvature guarantee (1{-}e^{-2\lambda})/(2\lambda) for \lambda\leq 1 , compared with the partial-monotonicity bound. (b)–(c) \lambda -sweep on Multi-News ( n{=}200 , k{=}10 , 100 examples): (b) the mean empirical trajectory-curvature proxy stays below the uniform-query reference bound 2\lambda for \lambda\leq 1 ; (c) the clipped trajectory guarantee is tighter than the uniform-query reference curve. Summary across applications. Symmetric functions: curvature subsumes specialized results ( c_{f}{=}2 recovers 0.432 without using symmetry). Decomposable objectives: curvature improves on additive bounds, which fail at moderate cost ratios. GCLin diversity: mean trajectory curvature follows the uniform-query reference curve 2\lambda and yields tighter per-instance curves. 5 Discussion and Conclusion Curvature provides a single, continuous parameter that extends the classical Conforti–Cornuéjols theory beyond monotonicity, giving the first curvature-controlled multiplicative guarantees for negative-valued submodular objectives. Greedy with pruning achieves (1-e^{-\bar{c}_{g}})/\bar{c}_{g} under cardinality constraints; DMCG-P extends this to general combinatorial constraints under explicit trajectory-curvature hypotheses. Experiments on three function classes confirm that the guarantees are conservative, and that trajectory-based curvature is often substantially tighter than worst-case bounds. A key limitation is that curvature is trajectory-specific: c_{g} certifies the realized greedy-with-pruning path, not an input parameter known before the algorithm runs. For decomposable objectives, the removal-marginal certificate (Proposition 4 ) gives an OPT-free post-hoc bound from the pruned trajectory, with OPT-aware and multilinear variants deferred to the appendix. Comparable certificates for broader value-oracle classes remain open. Concrete open directions include: (i) near-linear threshold or streaming variants that preserve the local pruning invariant; (ii) tight value-oracle lower bounds for curvature-controlled greedy under cardinality and matroid constraints; (iii) certificates for weighted relevance-minus-redundancy objectives, including nonuniform query weights; and (iv) algorithms that adapt pruning or selection to the observed trajectory curvature. Appendix A Additional Related Work Symmetric submodular functions. 10 proved that a variant of measured continuous greedy achieves (1-e^{-2})/2\approx 0.432 for maximizing a non-negative symmetric submodular function under a cardinality constraint. Section 4.1 explains how the same threshold follows from Proposition 3 : symmetric functions have c_{f}=2 , and hence c_{g}\leq 2 . More recently, 24 gave a deterministic O(kn) -query algorithm achieving the same 0.432 ratio for symmetric functions under a cardinality constraint, confirming the tractability of this class. Both results are specific to symmetric functions and require non-negativity, while our framework derives the same ratio from a single structural parameter that applies to all submodular functions, including those that go negative. Partial monotonicity. 17 introduced the monotonicity ratio m=\min_{S\subseteq T}f(T)/f(S) as a structural parameter for non-monotone submodular maximization, proving that standard greedy achieves m(1-1/e) and randomized greedy achieves m(1-1/e)+(1-m)/e under a cardinality constraint. Their framework requires f\geq 0 throughout. For symmetric functions, m=0 (since f(\emptyset)=f(N)=0 for cut functions), so the standard greedy guarantee is vacuous and the random greedy guarantee reduces to 1/e . In contrast, our curvature guarantee of (1-e^{-2})/2\approx 0.432 for symmetric functions strictly exceeds 1/e and uses a deterministic algorithm. More broadly, curvature and partial monotonicity capture different structural properties: the monotonicity ratio measures how much value can be lost by adding elements (a global property), while curvature measures the rate of diminishing returns along the greedy trajectory (a local property). Neither parameter dominates the other—functions with high curvature can have moderate monotonicity ratio and vice versa—but curvature applies to possibly-negative functions where partial monotonicity is undefined. The experimental comparison in Section 4 confirms the theoretical separation: the partial-monotonicity guarantee is either vacuous ( m=0 for symmetric-type instances) or inapplicable ( f<0 at moderate-to-high cost levels), while the curvature guarantee remains meaningful throughout. The GCLin analysis (Figure 2 ) further illustrates this: the curvature bound stays positive in regimes where the monotonicity-ratio bound vanishes, but the two parameters are incomparable in general. Distributional curvature. The multilinear curvature c_{F} is inherently distributional: it averages the pointwise curvature inequality over product distributions via the coupling in Theorem 3 . One can define a distributional curvature c_{D} as the expected curvature under random subset pairs drawn from such distributions. For strictly positive f , the coupling proof gives c_{D}=c_{F}=c_{f} : the distribution cannot improve on the worst case. For functions that go negative, c_{D} may be finite even when c_{F}=\infty , suggesting that distributional curvature could yield tighter bounds in some regimes. Comparison with additive guarantees. The additive-ratio framework of 11 —and its extensions [ 12 , 15 , 2 ] —gives f(S)\geq(1-1/e)\,g(O^{*})-\ell(O^{*}) for decomposable f=g-\ell . This becomes vacuous when \rho=\ell(O^{*})/g(O^{*})\geq 1-1/e . Subsequent works [ 12 , 15 , 19 , 2 ] extend distorted greedy to streaming, distributed, and stochastic settings, all inheriting the additive guarantee structure. The curvature framework provides a multiplicative alternative in the offline setting; extending it to streaming, distributed, and stochastic variants is a natural direction. Weak submodularity and generalizations. 6 studied maximization of \gamma -weakly submodular functions, which relax submodularity by a multiplicative ratio. The HFWK distorted greedy guarantee also incorporates the weak submodularity parameter. Our curvature is orthogonal: it measures diminishing-returns degradation (how much unions destroy value) rather than the submodularity gap. 1 studied DR-submodular maximization in continuous domains; our multilinear extension curvature c_{F} (Appendix G ) provides a bridge between the discrete and continuous settings: c_{F}=c_{f} when f is strictly positive, and c_{F}=\infty when f takes negative values (Theorem 3 ). Appendix B Greedy with Pruning: Pseudocode Input: oracle f , cardinality constraint k A_{0}\leftarrow\emptyset 1 for i\leftarrow 1 to k do 2 a_{i}\leftarrow\argmax_{x\in\mathcal{N}}\Delta\left(x|A_{i-1}\right) // break ties by the fixed ground-set order if \Delta\left(a_{i}|A_{i-1}\right)\leq 0 then 3 A_{k}\leftarrow A_{i-1} 4 break 5 A_{i}^{\prime}\leftarrow A_{i-1}\cup\{a_{i}\} 6 while \exists\,a\in A_{i}^{\prime} with \Delta\left(a|A_{i}^{\prime}\setminus\{a\}\right)\leq 0 do 7 choose the first such a in the fixed ground-set order 8 A_{i}^{\prime}\leftarrow A_{i}^{\prime}\setminus\{a\} 9 A_{i}\leftarrow A_{i}^{\prime} 10 return A_{k} 11 Algorithm 1 \textsc{Greedy}(f,k) Appendix C Measured Continuous Greedy Proof This appendix proves the conditional Theorem 6 (MCG guarantee) from the supporting step lemma plus the explicit monotonicity assumption below. MCG [ 10 , 5 ] operates on the multilinear extension of f subject to any downward-closed solvable polytope \mathcal{P} (matroid, knapsack, or their intersection, when a separation oracle for \mathcal{P} is available); the per-step analysis below depends only on this polytope structure and not on the specific constraint form. Lemma 1 ( 10 ) . For every 0\leq t1 , the MCG monotonicity condition above, and a downward-closed solvable polytope—measured continuous greedy returns a point \mathbf{y}(T) satisfying F(\mathbf{y}(T))\geq\frac{1-e^{-c_{f}T}-o(1)}{c_{f}}\,f\left(O^{*}\right), where O^{*} is an optimal feasible set and T\in[0,1] is the time horizon. Proof of Theorem 6 . We solve a scalar recurrence for a(t)\triangleq F(\mathbf{y}(t)) . From Lemma 1 , F(\mathbf{y}(t+\delta))-F(\mathbf{y}(t))\geq\delta\bigl[F(\mathbf{y}(t)\lor\mathbf{1}_{O^{*}})-F(\mathbf{y}(t))\bigr]-O(n^{3}\delta^{2})f\left(O^{*}\right). Apply Definition 3 with \mathbf{x}=\mathbf{1}_{O^{*}} and \mathbf{y}=\mathbf{y}(t) , using c_{F}=c_{f} (Theorem 3 (a)): F(\mathbf{y}(t)\lor\mathbf{1}_{O^{*}})-F(\mathbf{1}_{O^{*}})\geq(1-c_{f})\,F(\mathbf{y}(t)-\mathbf{y}(t)\land\mathbf{1}_{O^{*}}). Since \mathbf{y}(t)-\mathbf{y}(t)\land\mathbf{1}_{O^{*}}\leq\mathbf{y}(t) , Assumption 1 gives F(\mathbf{y}(t)-\mathbf{y}(t)\land\mathbf{1}_{O^{*}})\leq F(\mathbf{y}(t)) . Rearranging: F(\mathbf{y}(t)\lor\mathbf{1}_{O^{*}})-F(\mathbf{y}(t))\geq f\left(O^{*}\right)-F(\mathbf{y}(t))+(1-c_{f})F(\mathbf{y}(t))=f\left(O^{*}\right)-c_{f}\,F(\mathbf{y}(t)) . Combining with the MCG step: a(t+\delta)\geq(1-c_{f}\delta)\,a(t)+\delta(1-O(n^{3}\delta))f\left(O^{*}\right). Let m=T/\delta and unroll the recurrence from a(0)=0 : a(T)\geq\delta(1-O(n^{3}\delta))f\left(O^{*}\right)\sum_{r=0}^{m-1}(1-c_{f}\delta)^{r}. The geometric sum is \sum_{r=0}^{m-1}(1-c_{f}\delta)^{r}=\frac{1-(1-c_{f}\delta)^{m}}{c_{f}\delta}. Hence F(\mathbf{y}(T))\geq\frac{1-(1-c_{f}\delta)^{T/\delta}}{c_{f}}\,(1-O(n^{3}\delta))\,f\left(O^{*}\right). Taking the step size small enough that \delta\leq n^{-5} , and then sending \delta\to 0 , gives (1-c_{f}\delta)^{T/\delta}\to e^{-c_{f}T} and absorbs O(n^{3}\delta) into the o(1) term. ∎ Appendix D Computing the OPT-Free Curvature Certificate A key practical advantage of the greedy curvature framework over additive guarantees is that the algorithm can output a provable quality certificate alongside its solution, without access to the optimal set or its value. For decomposable objectives, pruning gives exactly the right observable denominators. D.1 The Removal-Marginal Certificate Given a decomposable objective f=g-\ell with g monotone submodular (CC curvature \alpha_{g} ) and \ell modular, let A_{0},A_{1},\ldots,A_{k} be the active-set trajectory of greedy with pruning. Define \hat{r}\;\triangleq\;\max_{i}\max_{e\in A_{i}}\frac{\ell(e)}{\Delta_{g}(e\mid A_{i}\setminus\{e\})}, with value 0 if all active sets are empty. This is the quantity used in Proposition 4 . The denominator is positive automatically. At the end of each pruning loop, every active element e\in A_{i} satisfies \Delta_{f}(e\mid A_{i}\setminus\{e\})=\Delta_{g}(e\mid A_{i}\setminus\{e\})-\ell(e)>0, and hence \Delta_{g}(e\mid A_{i}\setminus\{e\})>\ell(e) . Therefore \hat{r}<1 . The resulting certificate is \frac{f(A_{k})}{f(\text{OPT})}\;\geq\;\frac{1-e^{-\bar{\hat{c}}_{g}}}{\bar{\hat{c}}_{g}},\qquad\hat{c}_{g}=\frac{\alpha_{g}}{1-\hat{r}},\qquad\bar{\hat{c}}_{g}=\max\{1,\hat{c}_{g}\}. Proof of Proposition 4 . Let \mathcal{O}=\argmax_{|S|\leq k}f(S) . Fix O^{*}\in\mathcal{O} and a trajectory step i with f(A_{i}\setminus O^{*})>0 , since these are exactly the positive-denominator pairs in Definition 2 . Write A=A_{i} and T=A_{i}\setminus O^{*} . The first ingredient is the usual CC-curvature inequality for the monotone component g : g(O^{*}\cup A_{i})-g(O^{*})\;\geq\;(1-\alpha_{g})\,g(T). (2) To see this directly, enumerate T=\{e_{1},\ldots,e_{m}\} and telescope the gain from adding T to O^{*} . Each marginal of g is at least 1-\alpha_{g} times the corresponding marginal when the same element is added inside T ; summing gives ( 2 ). The second ingredient is the set-level penalty bound supplied by the removal marginals. Enumerate T=\{e_{1},\ldots,e_{m}\} again and write T_{0 gives \tau<1 , and ( 3 ) gives 0\leq\tau\leq\hat{r} . Combining ( 2 ) with modularity of \ell , \frac{f(O^{*}\cup A_{i})-f(O^{*})}{f(T)}\;\geq\;\frac{(1-\alpha_{g})g(T)-\ell(T)}{g(T)-\ell(T)}\;=\;\frac{(1-\alpha_{g})-\tau}{1-\tau}. The last expression is decreasing in \tau , since its derivative is -\alpha_{g}/(1-\tau)^{2} . Therefore \frac{f(O^{*}\cup A_{i})-f(O^{*})}{f(T)}\;\geq\;\frac{(1-\alpha_{g})-\hat{r}}{1-\hat{r}}\;=\;1-\frac{\alpha_{g}}{1-\hat{r}}. Taking the double minimum over O^{*}\in\mathcal{O} and qualifying trajectory steps in Definition 2 gives c_{g}\leq\alpha_{g}/(1-\hat{r}) . ∎ Remark 2 (Cheaper singleton diagnostic) . A cheaper quantity is the singleton ratio \hat{s}=\max_{e\in\cup_{i}A_{i}}\frac{\ell(e)}{g(\{e\})}. Since \Delta_{g}(e\mid A_{i}\setminus\{e\})\leq g(\{e\}) , the removal-marginal certificate is generally weaker: \hat{r}\geq\hat{s} . The singleton ratio can nevertheless be used as a formal certificate under the additional hypothesis \hat{s}<1-\alpha_{g} , in which case the singleton argument yields c_{g}\leq\alpha_{g}/(1-\hat{s}) . Without this extra hypothesis, singleton ratios are reported only as diagnostics in the experiments. Contrast with additive guarantees. The HFWK guarantee (1-1/e)\,g(\text{OPT})-\ell(\text{OPT}) requires knowledge of both g(\text{OPT}) and \ell(\text{OPT}) to evaluate. At test time on an instance where OPT is intractable, neither is available — one can only upper-bound g(\text{OPT}) (e.g., by the greedy value of g alone), which loosens the guarantee further. The removal-marginal certificate depends only on \alpha_{g} (a property of the function class, not the instance) and \hat{r} (observable from the algorithm’s own trajectory). D.2 Analytic \alpha_{g} for Application Classes The CC curvature \alpha_{g}=1-\min_{e,\,S\not\ni e}\Delta_{g}(e\mid S)/g(\{e\}) has closed-form expressions for the applications considered in this paper. Experimental design (Bayesian A-optimality). g(S)=\operatorname{tr}(\Sigma_{\text{prior}})-\operatorname{tr}(\Sigma_{S|}) , where \Sigma_{S|} is the posterior covariance after observing experiments in S . The CC curvature of g is determined by the eigenvalues of the information matrix: \alpha_{g}\;=\;1-\frac{\lambda_{\min}}{\lambda_{\max}}\;=\;1-\frac{1}{\kappa}, where \kappa is the condition number of X^{\top}X/\sigma^{2}+\Sigma_{\text{prior}}^{-1} and X is the design matrix. For well-conditioned designs ( \kappa\approx 2 ), \alpha_{g}\approx 0.5 ; for ill-conditioned designs ( \kappa\approx 20 ), \alpha_{g}\approx 0.95 . Coverage functions (directed vertex cover). g(S)=|\{j:j\text{ covered by some }v\in S\}| . Since any element’s coverage can be fully subsumed by the rest of the ground set, \min_{e,S}\Delta_{g}(e\mid S)=0 , giving \alpha_{g}=1 . This recovers the standard 1-1/e guarantee as a special case of the curvature framework. Feature selection (Gaussian mutual information). g(S)=\tfrac{1}{2}\log\det(I+\Sigma_{SS}/\sigma^{2}) , where \Sigma_{SS} is the covariance submatrix for features in S . The CC curvature depends on the spectral structure of the full covariance: \alpha_{g}\;=\;1-\frac{1}{\kappa(I+\Sigma/\sigma^{2})}, where \kappa(\cdot) denotes the condition number. When features are nearly independent, \alpha_{g}\approx 0 ; with high redundancy (correlated groups), \alpha_{g} approaches 1 . D.3 Computing \hat{r} from the Greedy Trajectory The certificate \hat{r} is computed from the pruned active sets A_{i} , not from the terminal output alone. For every element that is active at a step i , evaluate the removal marginal \Delta_{g}(e\mid A_{i}\setminus\{e\}) and form \frac{\ell(e)}{\Delta_{g}(e\mid A_{i}\setminus\{e\})}. The maximum over these ratios is \hat{r} . For decomposable objectives where g and \ell are given separately, this is a direct post-processing pass over the trajectory. The same pass also verifies \hat{r}<1 , although the pruning invariant already proves it. For the non-decomposable case (where only a value oracle for f is available), \hat{r} cannot be computed directly. However, the empirical greedy curvature c_{g} can still be bounded without decomposition — see the per-step curvature analysis in Appendix G . D.4 Relation to the Singleton Diagnostic Table 1 reports the guarantee (1-e^{-\bar{\hat{c}}_{g}})/\bar{\hat{c}}_{g} induced by the removal-marginal certificate (Proposition 4 ), which is the primary OPT-free bound for decomposable greedy with pruning. A cheaper singleton diagnostic \hat{s}=\max_{e\in\mathcal{A}}\ell(e)/g(\{e\}) is also computable and becomes a formal certificate under the additional condition in Remark 2 . Appendix E Experimental Setup This appendix provides full reproducibility details for the experiments in Section 4 . We organize results into two tiers: Tier 1 uses small instances ( n=20 , k=5 ) where exact OPT can be computed by brute-force enumeration, enabling ground-truth approximation ratios; Moderate-scale experiments use instances with n up to 300 , where OPT is intractable and only trajectory-based diagnostics are reported. Tier 1 instances ( n=20 , exact OPT). Each configuration uses k=5 and 10 random seeds (seeds 0 – 9 ). Exact OPT is computed by enumerating all subsets of size at most k . Experimental design (Bayesian A-optimality). A 20\times 5 design matrix X is generated with prescribed condition number \kappa=5 via SVD: X=U\diag(\sigma_{1},\ldots,\sigma_{5})V^{\top} where U,V are random orthogonal and \sigma_{i} are linearly spaced from 1 to \sqrt{5} . Prior: \Sigma_{\mathrm{prior}}=I_{5} ; noise variance \sigma^{2}=1 . g(S)=\tr(\Sigma_{\mathrm{prior}})-\tr(\Sigma_{S|}) is the variance reduction. Costs: \ell(e)=c_{s}\cdot\|x_{e}\|_{2}/\overline{\|x\|} where c_{s} is the cost scale and \overline{\|x\|} is the mean row norm. \alpha_{g}=1-1/\kappa=0.667 . Cost scales: c_{s}\in\{0,0.03,0.06,0.10,0.15,0.20,0.28\} . Coverage with costs. Random bipartite graph: n=20 vertices, m=40 items, each (vertex, item) edge included independently with probability 0.2 . g(S) = number of items covered by at least one vertex in S . Costs: \ell(v)=c_{s}\cdot\deg(v)/\overline{\deg} (degree-normalized). \alpha_{g}=1 . Cost scales: c_{s}\in\{0,0.5,1.0,2.0,3.5,5.0,8.0\} . Feature selection (mutual information minus \ell_{1} penalty). p=20 features in 4 correlated groups with pairwise within-group correlation 0.7 ; small cross-group noise ( 0.05\cdot Z for random Z , symmetrized and shifted to ensure positive definiteness). g(S)=\tfrac{1}{2}\log\det(I+\Sigma_{S,S}/\sigma^{2}) , \sigma^{2}=1 . Costs: \ell(e)=c_{s}\cdot(1+0.3\,\epsilon_{e}) , \epsilon_{e} standard normal, clipped to \geq 0.01 . \alpha_{g}\approx 0.79 . Cost scales: c_{s}\in\{0,0.05,0.1,0.2,0.3,0.5,0.8\} . Moderate-scale instances ( n up to 300 , trajectory diagnostics). Each configuration uses 5 seeds and 7 cost levels. OPT is intractable; the table reports the singleton curvature diagnostic (removal marginals were not recorded for these runs). Experimental design : n=200 , k=20 , d=10 , \kappa=5 ( \alpha_{g}=1-1/\kappa ). Cost scales: c_{s}\in\{0,0.02,0.05,0.10,0.15,0.22,0.30\} . Coverage : n=300 , k=30 , m=600 items, edge probability 0.05 ( \alpha_{g}=1 ). Cost scales: c_{s}\in\{0,0.5,1.5,3.0,5.0,8.0,12.0\} . Feature selection : n=100 , k=15 , 10 correlated groups. Cost scales: c_{s}\in\{0,0.03,0.08,0.15,0.25,0.4,0.6\} . \lambda -sweep (LLM summarization). Dataset: Multi-News [ 8 ] , a multi-document summarization benchmark. For each of 100 validation examples, source documents are chunked into 150-word passages padded with random distractors to reach n=200 , then embedded with TF-IDF vectors; pairwise cosine similarities define the GCLin objective (random seed 42 ). Greedy with best-prefix selection (the prefix A_{i} maximizing f(A_{i}) is returned, appropriate for non-monotone objectives) selects k=10 passages under \text{GCLin}_{\lambda} for \lambda\in\{0.1,0.25,0.5,0.75,1.0,1.5\} ( 2\lambda is the uniform-query reference bound for the five values with \lambda\leq 1 ; \lambda=1.5 is included as an empirical high-redundancy diagnostic). A local openai/gpt-oss-120b endpoint (prompt: “Summarize the following passages,” temperature 0.3 , max tokens 1024 ) summarizes the selected passages, and ROUGE-2 is computed against the reference summary. Algorithms. Tier 1 and MaxCut experiments use greedy+pruning (Algorithm 1 ) with lazy (priority-queue) evaluation; the \lambda -sweep uses greedy with best-prefix selection. The comparison baseline is distorted greedy [ 11 ] . The removal-marginal certificate \hat{r} (Proposition 4 ) is computed by a post-processing pass over the greedy trajectory, evaluating g(A_{i}) and g(A_{i}\setminus\{e\}) for each e\in A_{i} . Code and a CC BY 4.0 paper license will be released with the camera-ready version. Appendix F Additional Experimental Results This appendix contains figures and tables deferred from the main text. F.1 Tier 1: Cost-Sweep Curves Figure 3 shows the full cost-sweep curves for experimental design and coverage. GP is competitive with DG and often higher at larger costs, while the curvature guarantee stays positive as the HFWK bound goes negative. Figure 3 : Tier 1 cost sweeps ( n=20 , exact OPT). Solid lines: empirical ratios; dashed: theoretical guarantees. GP (blue) is competitive with DG (red) and often higher at larger costs. The curvature guarantee (dark blue) stays positive while the HFWK bound (dark red) goes negative at high costs. F.2 Tier 1: Curvature vs. Observed Ratios Figure 4 plots the empirical greedy curvature c_{g} (computed exactly using OPT) against the achieved f(S)/f(\text{OPT}) ratio. The curvature guarantee (1-e^{-\bar{c}_{g}})/\bar{c}_{g} follows the empirical trend in the non-monotone range (and the classical formula applies in the monotone small-curvature range). The removal-marginal certificate (reported in Table 1 ) provides a formal guarantee from the same trajectories. Figure 4 : Curvature vs. observed ratios ( n=20 , exact OPT). Each dot is a (curvature, ratio) pair from one instance. The curve is the theoretical guarantee, using the classical formula in the monotone small-curvature regime and (1-e^{-\bar{c}_{g}})/\bar{c}_{g} otherwise. GP ratios lie well above the curve. Arrows show the gap from the singleton diagnostic \hat{c}_{g} to the empirical c_{g} ; Proposition 4 gives the formal removal-marginal certificate. F.3 Moderate-Scale Instances (No Exact OPT) Table 2 : Moderate-scale results (no exact OPT; singleton diagnostics). f_{\text{GP}} and f_{\text{DG}} report mean f(S) over 5 seeds. Diag. is the multiplicative value of the singleton formula, included as a diagnostic rather than the formal removal-marginal certificate. HFWK uses heuristic best-known in place of OPT. Bold marks vacuous (negative) HFWK guarantees. Application Cost f_{\text{GP}} f_{\text{DG}} \hat{c}_{g} Diag. HFWK Exp. Design ( n{=}200 , k{=}20 ) 0.02 2.56 2.56 0.79 0.69 0.55 0.05 1.72 1.72 1.11 0.60 0.34 0.10 0.53 0.52 3.42 0.29 -0.42 0.15 0.05 0.04 44.3 0.05 -5.15 Coverage ( n{=}300 , k{=}30 ) 1.5 517 517 1.05 0.62 0.60 5.0 397 400 1.20 0.58 0.48 8.0 309 312 1.36 0.55 0.37 12.0 214 218 1.66 0.49 0.20 Feature Sel. ( n{=}100 , k{=}15 ) 0.08 5.63 5.62 1.06 0.62 0.58 0.25 4.14 4.14 1.57 0.51 0.44 0.40 2.88 2.82 2.85 0.34 0.20 0.60 1.32 1.23 55.0 0.05 -0.40 Figure 5 : Moderate-scale experiments (no exact OPT). Left panels: f(S) values; GP (blue) matches or exceeds DG (red). Right panels: singleton curvature diagnostics (purple) vs HFWK (dark red). Diagnostics remain positive across all cost levels tested (removal marginals were not recorded for these runs). Results. GP and DG achieve similar solution quality on most instances, with GP producing slightly better values at high costs (e.g., f_{\text{GP}}=2.88 vs f_{\text{DG}}=2.82 for feature selection at cost 0.40 ). The singleton curvature diagnostic stays positive at every cost level. The HFWK bound becomes vacuous on experimental design at cost 0.10 ( \rho\geq 0.63 ) and on feature selection at cost 0.60 . The displayed values are diagnostics rather than certified guarantees; the formal certificate in Appendix D requires removal-marginal post-processing along the trajectory. F.4 Curvature vs. Additive Guarantee Comparison Table 3: Curvature vs. HFWK additive guarantee (as multiples of f(O^{*}) ). HFWK uses 1-1/(e(1-\rho)) ; curvature uses c_{g}\leq\alpha_{g}/(1-r) (Proposition 11 ). Application \alpha_{g} \rho HFWK Curvature Exp. design (low) 1 0.1 0.591 \geq 0.604 Exp. design (med) 1 0.4 0.387 \geq 0.487 Exp. design (high) 1 0.6 0.080 \geq 0.367 Feature sel. ( \alpha_{g}\!=\!0.5 ) 0.5 0.3 0.474 \geq 0.715 Feature sel. ( \alpha_{g}\!=\!0.5 ) 0.5 0.5 0.264 \geq 0.632 Vertex cover 1 0.5 0.264 \geq 0.432 Table 3 compares the curvature and HFWK frameworks across applications from the additive-ratio literature. The curvature guarantee dominates whenever the cost ratio \rho exceeds approximately 0.15 (for coverage-type g with \alpha_{g}=1 ). F.5 MaxCut: Symmetric Submodular Functions We test whether greedy+pruning (Algorithm 1 ) improves on standard greedy for cardinality-constrained MaxCut, a canonical symmetric submodular function with c_{f}=2 . By Proposition 3 and Theorem 1 , the guarantee is (1-e^{-2})/2\approx 0.432 . Objective. Given an undirected graph G=(V,E) with |V|=n , the MaxCut objective is f(S)=|\delta(S)|=|\{(u,v)\in E:u\in S,v\notin S\}| , subject to |S|\leq k . Instance families. Planted distractor (stochastic block model). Three communities of sizes |A|=k , |B|=k , |C|=n-2k . Edge probabilities: p_{AA}=0.8 , p_{BB}=0.2 , p_{CC}=0.3 , p_{AB}=0.3 , p_{AC}=p_{BC}=0.4 . Community A is a dense “bait” cluster whose high-degree vertices attract greedy early, but whose intra-cluster edges become cut-reducing once many A -vertices are selected. Erdős–Rényi. Homogeneous baseline: each edge present independently with probability p=0.3 . Configurations. n\in\{16,20\} , k\in\{\lfloor n/4\rfloor,\lfloor n/3\rfloor,\lfloor n/2\rfloor\} , giving 12 configurations (6 planted distractor, 6 Erdős–Rényi). Each configuration uses 20 random seeds. Table 4 reports the 8 configurations where pruning activates on at least one seed; the 4 remaining Erdős–Rényi configurations ( k\leq n/3 ) are omitted because GP and greedy coincide on homogeneous graphs at these budgets. Algorithms. Standard greedy, greedy+pruning (Algorithm 1 ), and random greedy [ 3 ] . OPT. Exact enumeration over all subsets of size at most k . Reproducibility. Graph generation is deterministic: numpy.RandomState with seed \mathtt{seed}\times 1000+n\times 100+k . Code: experiments/objectives/maxcut.py (objective and graph generators) and experiments/run_maxcut.py (runner). Full results: experiments/results/maxcut_results.json (720 records). Results. Table 4 reports mean approximation ratios (relative to exact OPT) and the number of instances where greedy+pruning (GP) strictly beats standard greedy. Table 4: MaxCut experiment: mean f(S)/f(O^{*}) over 20 seeds. “GP > Greedy” counts instances where pruning strictly improves on standard greedy. Theory guarantee: (1-e^{-2})/2\approx 0.432 . Instance type n k Greedy GP Random GP > Greedy Planted distractor 16 4 0.979 0.979 0.947 0/20 Planted distractor 16 5 0.974 0.974 0.956 0/20 Planted distractor 16 8 0.935 0.966 0.911 13/20 Planted distractor 20 5 0.980 0.980 0.957 0/20 Planted distractor 20 7 0.975 0.975 0.937 0/20 Planted distractor 20 10 0.956 0.975 0.915 12/20 Erdős–Rényi 16 8 0.971 0.986 0.895 6/20 Erdős–Rényi 20 10 0.966 0.981 0.922 9/20 At small budgets ( k\leq n/3 ), pruning never activates: greedy does not over-commit, so GP and greedy coincide. At k\approx n/2 , greedy selects vertices whose neighbors increasingly fall inside S , reducing cut value. Pruning detects these ( f(v\mid S\setminus\{v\})\leq 0 ) and ejects them, freeing slots for better choices. On planted-distractor graphs the effect is strongest (GP wins 13/20 at n{=}16 , k{=}8 ; 12/20 at n{=}20 , k{=}10 ), because the dense bait cluster A traps greedy more reliably. Erdős–Rényi graphs show a weaker but still present effect (6–9 wins out of 20). Overall, GP strictly improves on greedy in 40 of 240 instances (16.7%), concentrated in the k=n/2 regime. All observed ratios far exceed the (1-e^{-2})/2\approx 0.432 guarantee, confirming that the bound is conservative while the pruning mechanism produces measurable empirical gains. Appendix G Multilinear Extension, DMCG-P, and MCG This appendix contains the multilinear extension analysis, the DMCG-P algorithm and its guarantees, and a conditional MCG comparison for strictly positive functions satisfying the standard MCG monotonicity lemma. These results extend the discrete greedy guarantee of Theorem 1 from cardinality constraints to integral feasible-set hulls for DMCG-P, and to the standard continuous setting for MCG. G.1 Curvature of the Multilinear Extension We now lift curvature to the continuous relaxation. The multilinear extension is the standard bridge between discrete submodular optimization and continuous relaxations—it underlies the measured continuous greedy algorithm (Section G.3 ) and the correlation gap framework [ 5 ] . The question is whether curvature lifts cleanly to this continuous setting. Classical non-monotone algorithms (e.g., BFNS randomized greedy [ 3 ] , measured continuous greedy) analyze the multilinear extension and rely on the correlation gap: each step of the continuous relaxation bounds F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{x}) from below using F(\mathbf{y}-\mathbf{x}\land\mathbf{y}) . In the coupled set-level view, one wants a lower bound on f\left(R_{1}\cup R_{2}\right)-f\left(R_{1}\right) in terms of f\left(R_{2}\right) for disjoint realizations R_{1},R_{2} . Zero-valued sets are delicate: if f\left(R_{2}\right)=0 , submodularity only gives the upper bound f\left(R_{1}\cup R_{2}\right)-f\left(R_{1}\right)\leq 0 , not the lower bound needed for a positive-denominator curvature comparison. Our curvature framework makes this precise: strict positivity of f turns out to be the key structural property. For a set function f:2^{\mathcal{N}}\to\mathbb{R} , its multilinear extension F:[0,1]^{\mathcal{N}}\to\mathbb{R} is F(\mathbf{x})=\mathbb{E}\left[f\left(\mathcal{R}(\mathbf{x})\right)\right]=\sum_{R\subseteq\mathcal{N}}f\left(R\right)\prod_{i\in R}x_{i}\prod_{j\notin R}(1-x_{j}), where \mathcal{R}(\mathbf{x}) includes each i independently with probability x_{i} . Definition 3 (Multilinear curvature) . The curvature c_{F} of the multilinear extension is c_{F}=1-\min_{\begin{subarray}{c}\mathbf{x},\mathbf{y}\in[0,1]^{\mathcal{N}}\\ F(\mathbf{y}-\mathbf{x}\land\mathbf{y})>0\end{subarray}}\frac{F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{x})}{F(\mathbf{y}-\mathbf{x}\land\mathbf{y})}. As in Definition 1 , the minimum ranges only over positive-denominator pairs, and we set c_{F}=\infty if the admissible ratios are unbounded below. The multilinear curvature is inherently distributional : it averages the pointwise curvature inequality over coupled product distributions. The coupling proof below makes this explicit. Proposition 6 (Discrete curvature bounds multilinear curvature) . c_{f}\leq c_{F} . Proof. The discrete vertices \{0,1\}^{\mathcal{N}}\subset[0,1]^{\mathcal{N}} , and every positive-denominator pair in Definition 1 is an admissible pair in Definition 3 , so the minimum defining c_{F} ranges over a larger domain. ∎ Proposition 7 ( c_{F}=\infty for negative functions) . Suppose f is normalized submodular and f\left(e\right)>0 for every singleton e\in\mathcal{N} . If f takes a negative value, then c_{F}=\infty . Intuitively, the denominator F(\mathbf{z}_{\varepsilon}) in the curvature ratio can be driven to zero by concentrating mass on an inclusion-minimal negative set, while the numerator remains bounded away from zero by that set’s negative value. This concentration structure motivates the pruning invariant introduced in § G.2 . Proof idea. Let \mathcal{N}^{\prime} be an inclusion-minimal set with f\left(\mathcal{N}^{\prime}\right)<0 ; minimality gives f\left(S\right)\geq 0 for all S\subsetneq\mathcal{N}^{\prime} . Construct \mathbf{z}_{\varepsilon}=\varepsilon\,\mathbf{1}_{\mathcal{N}^{\prime}\setminus\{e^{\prime}\}}+\mathbf{1}_{\{e^{\prime}\}} so that the denominator F(\mathbf{z}_{\varepsilon}) interpolates continuously from f\left(e^{\prime}\right)>0 (by singleton positivity) to f\left(\mathcal{N}^{\prime}\right)<0 , crossing zero at some \varepsilon_{0} . The numerator stays at most f\left(\mathcal{N}^{\prime}\right)<0 throughout, so the ratio diverges as \varepsilon\to\varepsilon_{0}^{-} . See Appendix J for the complete construction. ∎ The following is the key structural result connecting pointwise and distributional curvature. Theorem 3 (Strict positivity characterization) . Let f:2^{\mathcal{N}}\to\mathbb{R} be normalized submodular with f\left(e\right)>0 for every singleton e\in\mathcal{N} . (a) If f is strictly positive ( f\left(S\right)>0 for every nonempty S ), then c_{f}=c_{F} . (b) If f takes a negative value, then c_{F}=\infty . Proof idea. Part (b) is Proposition 7 . For part (a), we construct a product-distribution coupling (R_{1},R_{2}) with disjoint supports matching the multilinear marginals. Strict positivity ensures f\left(R_{2}\right)>0 whenever R_{2}\neq\emptyset , so the discrete curvature inequality applies realization-by-realization and survives expectation: c_{F}\leq c_{f} . See Appendix J for the full coupling construction. Remark 3 (Strict positivity and the continuous relaxation) . Theorem 3 identifies strict positivity as a sufficient condition under which pointwise curvature (a combinatorial, worst-case property) lifts perfectly to the multilinear extension (a continuous, averaged property). When f is strictly positive, c_{F}=c_{f} ; MCG gives the stated global-curvature comparison when its trajectory monotonicity lemma also applies. When f takes negative values, c_{F}=\infty ; the curvature guarantees in this paper therefore use trajectory-restricted quantities, either for discrete greedy with pruning (§ 2.2 ) or for its multilinear counterpart DMCG-P (§ G.2 ). The gap between strict positivity and non-negativity is genuine: non-negative functions with f\left(S\right)=0 for some nonempty S can have c_{F}>c_{f} (see Section 5 ). G.2 Fractional Greedy with Pruning (DMCG-P) The discrete algorithm of the previous subsection is tied to cardinality constraints; integral feasible-set hull constraints beyond cardinality can be handled by multilinear relaxations. But Theorem 3 showed that c_{F}=+\infty as soon as f takes a negative value, so the classical multilinear analysis—which routes through c_{F} —breaks down. We resolve this by mirroring the discrete construction: define a trajectory-restricted fractional curvature c_{g}^{F} , and prune to keep only positive-slope active coordinates. The key analytical ingredients are a slope invariant showing that pruning preserves the trajectory structure needed in the descent proof and an elementwise multilinear Conforti–Cornuéjols inequality lifting the discrete curvature bound to the continuous setting. The resulting algorithm—a pruning variant of the standard fixed-step discretization of measured continuous greedy [ 10 ] —we call DMCG-P (Discretized Measured Continuous Greedy with Pruning). The algorithm itself is a combination of known ingredients; the contribution is in the analysis : the structural observation that pruning keeps the trajectory away from the concentration witnesses of Proposition 7 , and the resulting (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F} guarantee for arbitrary submodular f with finite c_{g}^{F} . Full proofs appear in Appendix H . G.2.1 The DMCG-P Algorithm Let \mathcal{I}\subseteq 2^{\mathcal{N}} be a downward-closed family of feasible sets, let \mathcal{P}=\operatorname{conv}\{\mathbf{1}_{S}:S\in\mathcal{I}\} , and assume exact linear optimization over \mathcal{I} (equivalently over \mathcal{P} ). For submodular f , write F:[0,1]^{\mathcal{N}}\to\mathbb{R} for the multilinear extension and \partial_{j}F(\mathbf{x})=F(\mathbf{x}\mid x_{j}=1)-F(\mathbf{x}\mid x_{j}=0) for the multilinear slope; by multilinearity, \partial_{j}F is independent of x_{j} . Input: multilinear oracle F of submodular f , \mathcal{P}=\operatorname{conv}\{\mathbf{1}_{S}:S\in\mathcal{I}\} for a downward-closed family \mathcal{I} , step count T\in\mathbb{N} \tilde{S}_{0}\leftarrow\mathbf{0} 1 for i\leftarrow 0 to T-1 do 2 B_{i}\leftarrow\arg\max_{B\in\mathcal{I}}\sum_{j\in B}\partial_{j}F(\tilde{S}_{i}) 3 // exact linear optimization v_{i}\leftarrow\mathbf{1}_{B_{i}} 4 S_{i+1}\leftarrow\tilde{S}_{i}+\tfrac{1}{T}\,v_{i} 5 \tilde{S}_{i+1}\leftarrow S_{i+1} 6 while \exists\,j with (\tilde{S}_{i+1})_{j}>0 and \partial_{j}F(\tilde{S}_{i+1})\leq 0 do 7 (\tilde{S}_{i+1})_{j}\leftarrow 0 8 return \tilde{S}_{T} 9 Algorithm 2 \textsc{DMCG-P}(F,\mathcal{P},T) — Discretized Measured Continuous Greedy with Pruning Integral selection. Because \mathcal{P} is the convex hull of feasible incidence vectors, the linear optimization step can be written directly over B_{i}\in\mathcal{I} , and the selected direction is the integral vector v_{i}=\mathbf{1}_{B_{i}} used in the analysis. The pruning loop supplies the slope invariant used below: every surviving coordinate of \tilde{S}_{i} has strictly positive multilinear slope \partial_{j}F(\tilde{S}_{i})>0 . This keeps the trajectory away from the specific concentration witnesses that drive c_{F}=\infty in the proof of Proposition 7 , but finiteness of the trajectory curvature is still stated as an explicit hypothesis. Definition 4 (Fractional greedy curvature) . Let \mathcal{O}=\argmax_{S\in\mathcal{I}}f\left(S\right) and let \tilde{S}_{0},\dots,\tilde{S}_{T-1} be the iterates of Algorithm 2 . The fractional greedy curvature along the trajectory is c_{g}^{F}\;=\;1\;-\;\min_{O^{*}\in\mathcal{O}}\;\min_{\begin{subarray}{c}0\leq i0\end{subarray}}\;\frac{F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\mathbf{1}_{O^{*}})}{F(\tilde{S}_{i}-\tilde{S}_{i}\land\mathbf{1}_{O^{*}})}. Definition 4 is the exact multilinear analogue of the discrete greedy curvature c_{g} (Definition 2 ): the minimization is over iterates, not the whole cube, and only positive-denominator pairs are admissible. Lemma 2 below gives the positive-slope invariant used in the proof; finiteness of c_{g}^{F} is kept as a theorem hypothesis or supplied by an application-specific certificate. Lemma 2 (Non-negative multilinear slope after pruning) . For every i\geq 1 and every j\in\mathcal{N} , either (\tilde{S}_{i})_{j}=0 or \partial_{j}F(\tilde{S}_{i})>0 . Proof. Direct from the while-loop termination condition in Algorithm 2 ; see Lemma 5 in Appendix H for the full statement and surrounding structural lemmas. ∎ G.2.2 DMCG-P for general submodular f The headline result of this subsection is that DMCG-P delivers a curvature-aware (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F} guarantee for arbitrary submodular f on such an integral feasible-set hull, with no monotonicity or non-negativity assumption. The only hypothesis beyond submodularity is that the trajectory-restricted curvature c_{g}^{F} of Definition 4 is finite and the run is in the step-size regime \delta\bar{c}_{g}^{F}\leq 1 for \bar{c}_{g}^{F}=\max\{1,c_{g}^{F}\} and step size \delta=1/T —always achievable by choosing T large enough. Pruning controls the trajectory through the positive-slope invariant, and the descent argument of Theorem 1 lifts to the multilinear setting using only submodularity and the slope invariant—never monotonicity of f . Theorem 4 (General DMCG-P guarantee) . Let \mathcal{I}\subseteq 2^{\mathcal{N}} be downward-closed, let \mathcal{P}=\operatorname{conv}\{\mathbf{1}_{S}:S\in\mathcal{I}\} , and assume exact linear optimization over \mathcal{I} . Let f:2^{\mathcal{N}}\to\mathbb{R} be submodular, let O^{*}\in\argmax_{S\in\mathcal{I}}f\left(S\right) , and let c_{g}^{F}\in[0,\infty) be the trajectory-restricted fractional greedy curvature of Definition 4 . Put \bar{c}_{g}^{F}=\max\{1,c_{g}^{F}\} . Assume c_{g}^{F}<\infty , \delta\bar{c}_{g}^{F}\leq 1 for step size \delta=1/T . Then \textsc{DMCG-P}(F,\mathcal{P},T) returns \tilde{S}_{T}\in\mathcal{P} with F(\tilde{S}_{T})\;\geq\;\frac{1-e^{-\bar{c}_{g}^{F}}}{\bar{c}_{g}^{F}}\,f\left(O^{*}\right)\;-\;\frac{n(n-1)\,C_{F}}{T}, where n=|\mathcal{N}| , and C_{F}=\max_{j\neq\ell,\,\mathbf{x}\in[0,1]^{\mathcal{N}}}|\partial_{j\ell}F(\mathbf{x})| is the smoothness constant. The step count T is independent of the constraint; choosing T large makes the discretization error negligible. No monotonicity or non-negativity of f is required; the finite-curvature condition is an explicit trajectory hypothesis using the positive-denominator convention of Definition 4 . The full proof is given in Appendix H as Theorem 7 , via the per-step descent Lemma 6 . The proof is a line-by-line lift of the non-monotone branch of the discrete proof of Theorem 1 : each discrete inequality (pruning, greedy selection, submodularity, curvature, and the slope invariant on the active set) has an immediate multilinear analogue via the standard properties of the multilinear extension [ 5 ] , and the per-step recurrence closes in the same form modulo an O(1/T) discretization correction. The appendix states the finite- T bound for \delta\bar{c}_{g}^{F}\leq 1 , which yields the displayed fixed-curvature asymptotic. Unlike discrete greedy, where each step adds one element and the step count equals k , the continuous greedy permits finer discretization: choosing T>k reduces the error without changing the constraint. Two consequences are worth stating explicitly. First, in the strictly positive case c_{g}^{F}\leq c_{F}=c_{f} (Theorem 3 (a)), so Theorem 4 recovers the classical continuous-greedy guarantee [ 5 ] ; when c_{g}^{F}0 for every nonempty S ), where c_{F}=c_{f} (Theorem 3 (a)). DMCG-P also covers this case via c_{g}^{F}\leq c_{f} , with the sharper small-curvature formula supplied by monotonicity. How to bound c_{g}^{F} . (i) When f is monotone submodular, c_{g}^{F}\leq c_{f}\in[0,1] automatically. (ii) When f=g-\ell is decomposable, a closed-form certificate bounds c_{g}^{F} from the pruned trajectory alone (Section 4.2 ), covering decomposable negative- f cases. Table 5 summarizes the two regimes of this subsection. The DMCG-P row is the headline Theorem 4 : whenever the trajectory curvature c_{g}^{F} is finite and \delta\bar{c}_{g}^{F}\leq 1 —with decomposable certificates providing one concrete way to verify this—DMCG-P delivers the (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F} bound regardless of monotonicity or sign of f . The wDMCG-P row is the complementary non-negative non-monotone regime, where c_{g}^{F} need not be bounded and the correlation-gap analysis recovers a regime-independent 1/e . Under the additional hypotheses of strict positivity and the standard MCG monotonicity lemma, the classical measured continuous greedy analysis offers an alternative (1-e^{-c_{f}})/c_{f} bound parameterized by the globally-computable set-function curvature c_{f} , via the equality c_{F}=c_{f} of Theorem 3 (a). The next subsection records this result. G.3 Measured Continuous Greedy We record a conditional classical comparison for measured continuous greedy (MCG). DMCG-P already covers this regime via Theorem 4 : when f is strictly positive, c_{g}^{F}\leq c_{F}=c_{f}<\infty (Theorem 3 (a)), so DMCG-P delivers the \bar{c}_{g}^{F} -parameterized guarantee above. The measured continuous greedy (MCG) guarantee below is parameterized by the global curvature c_{f} rather than the trajectory-restricted c_{g}^{F} . Its advantage is that c_{f} is a known quantity for certain function classes (e.g., graph-cut functions have c_{f}=2 ), whereas bounding c_{g}^{F} may require a per-instance certificate. Its disadvantage is that it requires both strict positivity and the standard MCG monotonicity lemma stated in Appendix C ; it does not apply when f takes negative values, and it cannot exploit c_{g}^{F}1 (the non-monotone case; for c_{f}\leq 1 , f is monotone by Proposition 1 ), and \mathcal{P} a downward-closed solvable polytope. Assume the MCG trajectory satisfies Assumption 1 . Then MeasuredContinuousGreedy returns \mathbf{y}(T) with F(\mathbf{y}(T))\geq\frac{1-e^{-c_{f}T}-o(1)}{c_{f}}\,f\left(O^{*}\right), where O^{*}\in\argmax_{\mathbf{1}_{S}\in\mathcal{P}}f\left(S\right) and T\in[0,1] . Appendix H DMCG-P: Full Proofs This appendix contains the full proofs for Section G.2 . The headline result is Theorem 7 : DMCG-P achieves a (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F} multiplicative guarantee for arbitrary submodular f with finite trajectory curvature c_{g}^{F} , including functions that take negative values. For decomposable f=g-\ell , Proposition 9 provides a closed-form certificate c_{g}^{F}\leq\alpha_{g}/(1-\hat{r}_{F}) from the pruned trajectory, making the guarantee concrete without access to OPT. This is the fractional analogue of the discrete decomposable certificate used for the applications. We first recall the setup and algorithm reference (§ H.1 ), then establish the structural lemmas needed for the analysis (§ H.2 ), and prove the headline DMCG-P guarantee (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F}\cdot f(O^{*}) for arbitrary submodular f with finite trajectory curvature c_{g}^{F} via the fractional greedy curvature c_{g}^{F} tailored to the DMCG-P trajectory (§ H.3 ). No monotonicity or non-negativity of f is required: the analysis is a direct line-by-line lift of the discrete greedy proof (Theorem 1 ) to the multilinear setting, and each step uses only submodularity or the pruning slope invariant (Lemma 5 ). Section H.4 then establishes the decomposable-structure certificate c_{g}^{F}\leq\alpha_{g}/(1-\hat{r}_{F}) , making § H.3 concrete on negative-valued f , and Section H.5 handles the complementary non-negative non-monotone regime via damped weighted DMCG-P. Throughout this appendix, ratios of the form (1-e^{-c})/c and (1-(1-c/T)^{T})/c are interpreted by continuous extension at c=0 when the small-curvature monotone analysis is invoked. H.1 Setup and Algorithm Reference Throughout §§ H.1 – H.3 we work with a downward-closed family of feasible sets \mathcal{I}\subseteq 2^{\mathcal{N}} and its integral hull P=\operatorname{conv}\{\mathbf{1}_{B}:B\in\mathcal{I}\}\subseteq[0,1]^{\mathcal{N}} . We assume exact linear optimization over \mathcal{I} (equivalently over P ) is available. This includes matroid independent-set polytopes and other explicitly integral feasible-set hulls, but not an arbitrary fractional downward-closed relaxation unless it is represented as such a hull. We write b=\max_{B\in\mathcal{I}}|B| . For f:2^{\mathcal{N}}\to\mathbb{R} submodular, the multilinear extension F:[0,1]^{\mathcal{N}}\to\mathbb{R} is F(\mathbf{x})\;=\;\mathbb{E}_{R\sim\mathbf{x}}[f(R)]\;=\;\sum_{R\subseteq\mathcal{N}}f(R)\prod_{i\in R}x_{i}\prod_{j\notin R}(1-x_{j}), where R includes each i independently with probability x_{i} . For a coordinate j\in\mathcal{N} let \partial_{j}F(\mathbf{x})=F(\mathbf{x}\mid x_{j}=1)-F(\mathbf{x}\mid x_{j}=0) ; by multilinearity, \partial_{j}F is independent of x_{j} . Algorithm 2 gives the DMCG-P procedure used throughout this appendix. Three details of Algorithm 2 are used repeatedly. (i) The selection rule on Line 2 uses the unweighted gradient: it maximises \langle\nabla F(\tilde{S}_{i}),\,\mathbf{1}_{B}\rangle over B\in\mathcal{I} , not the Measured-Continuous-Greedy weighted form with multiplier (1-(\tilde{S}_{i})_{j}) on each coordinate. Since P=\operatorname{conv}\{\mathbf{1}_{B}:B\in\mathcal{I}\} , this is equivalent to linear optimization over P , and the selected direction is the integral vector v_{i}=\mathbf{1}_{B_{i}} used in the analysis. The analysis in § H.3 shows that the unweighted form suffices: Lemma 5 (non-negative surviving slopes) is exactly what lets one turn a weighted swap bound into an unweighted one. (ii) After the final iteration, \tilde{S}_{T} lies in the downward-closed polytope P but need not itself be integral; pruning may have reduced total mass below b . If an integral output is required, one may apply a rounding method for points in integral hulls, such as swap rounding or pipage rounding, to \tilde{S}_{T}\in P . (iii) The pruning loop is written with a nonstrict inequality \partial_{j}F\leq 0 on Line 2 . As in Section 2.2 , this ensures that after pruning every surviving coordinate has strictly positive multilinear slope (Lemma 5 below), which is what drives the multilinear curvature argument. H.2 Structural Lemmas We collect here the facts about DMCG-P that underlie the analysis. All lemmas hold for any submodular f (monotone or not), unless noted. Lemma 3 (Feasibility) . For every i\in\{0,1,\dots,T\} , the iterate \tilde{S}_{i} lies in the downward-closed polytope P and satisfies \tilde{S}_{i}\in[0,1]^{\mathcal{N}} . In particular, (\tilde{S}_{i})_{j}\leq i/T for every coordinate j . Proof. We show \tilde{S}_{i}\leq\frac{1}{T}\sum_{\tau0 by 0 changes the value by F(\mathbf{x}-x_{j}\mathbf{e}_{j})-F(\mathbf{x})=-x_{j}\,\partial_{j}F(\mathbf{x}). The pruning rule fires only when \partial_{j}F(\mathbf{x})\leq 0 , so the displayed change is non-negative, and it is strict when the slope is strictly negative. Applying this argument to each pass of the while-loop gives F(\tilde{S}_{i+1})\geq F(S_{i+1}) . ∎ Lemma 5 (Nonneg. slope after pruning) . At every iterate \tilde{S}_{i} (for i\geq 1 ) and every j\in\mathcal{N} , either (\tilde{S}_{i})_{j}=0 or \partial_{j}F(\tilde{S}_{i})>0 . Proof. Direct from the pruning loop termination condition (Line 2 ): the loop exits exactly when no coordinate has both positive value and non-positive slope. ∎ Lemma 5 is the structural property that replaces the pointwise curvature argument when f is allowed to be negative. In ordinary MCG, c_{F} can diverge because the definition of c_{F} ranges over all \mathbf{x}\in[0,1]^{\mathcal{N}} , in particular over witnesses of the form \mathbf{x}_{\varepsilon}=(1-\varepsilon)\mathbf{1}_{\mathcal{N}^{\prime}\setminus\{e^{\prime}\}} from Proposition 7 , which concentrate mass on inclusion-minimal sets with f<0 . Lemma 5 shows that DMCG-P’s iterates never lie at such witnesses: at each \tilde{S}_{i} , every active coordinate has positive multilinear slope, so the iterate avoids the neighbourhood where multilinear curvature blows up. Remark 4 (Slope signs after pruning) . A coordinate whose slope is non-positive at one iterate need not keep a non-positive slope forever. Pruning may reduce (\tilde{S}_{i})_{k} for some k\neq j , which by submodularity can increase \partial_{j}F and flip its sign. The useful invariant is the weaker one stated in Lemma 5 : after each pruning loop terminates, every coordinate with positive mass has positive slope. Within a stretch of iterations without pruning, slopes are monotone non-increasing, but the proof below uses only the post-pruning invariant. H.3 General DMCG-P Guarantee We now prove the headline analytic result: unweighted DMCG-P (Algorithm 2 ) on an arbitrary submodular objective f over the integral feasible-set hull P=\operatorname{conv}\{\mathbf{1}_{B}:B\in\mathcal{I}\} matches the classical continuous-greedy guarantee (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F}\cdot f(O^{*}) in the T\to\infty limit, with c_{g}^{F} a trajectory-restricted multilinear analogue of the greedy curvature c_{g} of Definition 2 . No monotonicity or non-negativity of f is assumed; the only hypothesis is that the trajectory admits a finite curvature certificate. Lemma 5 supplies the pruning invariant used in the descent proof, but it is not by itself a global finiteness theorem for all possible denominators. The proof is a direct line-by-line lift of the discrete argument for Theorem 1 : each discrete inequality—pruning, greedy selection, submodularity, curvature, and the slope invariant on the active set (Lemma 5 )—has a multilinear analogue spelled out below, requiring only submodularity of f or finite on-trajectory slope, never monotonicity of f . The per-step recurrence closes in exactly the same form, modulo a discretisation correction of size O(1/T) . We state the finite- T bound in the regime \bar{c}_{g}^{F}\leq T (equivalently \delta\bar{c}_{g}^{F}\leq 1 for step size \delta=1/T ), which is always achievable by choosing T large enough for any fixed finite trajectory curvature. This is deliberately different from the conditional MCG comparison in Appendix C : DMCG-P does not assume a global coordinate-zeroing monotonicity lemma, but enforces the local positive-slope condition needed for Step 7 by pruning. Key inequalities. The analysis relies on three elementary properties of the multilinear extension of a submodular f . Let \mathbf{x},\mathbf{y}\in[0,1]^{\mathcal{N}} and \mathbf{d}\in\mathbb{R}_{\geq 0}^{\mathcal{N}} with \mathbf{x},\mathbf{x}+\mathbf{d}\in[0,1]^{\mathcal{N}} . (P1) Concavity along non-negative directions. The map t\mapsto F(\mathbf{x}+t\mathbf{d}) is concave on [0,\min_{j}\{(1-x_{j})/d_{j}:d_{j}>0\}] [ 5 , §2.3] . (P2) Tangent bounds. By (P1), F(\mathbf{x}+\mathbf{d})-F(\mathbf{x})\leq\langle\nabla F(\mathbf{x}),\,\mathbf{d}\rangle (upper tangent at the left endpoint), and equivalently F(\mathbf{x}+\mathbf{d})-F(\mathbf{x})\geq\langle\nabla F(\mathbf{x}+\mathbf{d}),\,\mathbf{d}\rangle (lower tangent at the right endpoint). (P3) Submodular union bound. F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{x})\leq\sum_{j}(1-x_{j})\,y_{j}\,\partial_{j}F(\mathbf{x}). Proof. Telescope coordinate-wise from \mathbf{x} to \mathbf{x}\lor\mathbf{y} , changing coordinate j (for which y_{j}>x_{j} ) from x_{j} to y_{j}\lor x_{j} ; the per-coordinate gain is (y_{j}-x_{j})_{+}\,\partial_{j}F(\cdot) evaluated at the intermediate point, bounded above by (y_{j}-x_{j})_{+}\,\partial_{j}F(\mathbf{x}) by submodularity (cross-partials \leq 0 ). Summing and using (y_{j}-x_{j})_{+}\leq(1-x_{j})y_{j} for y_{j}\in[0,1] gives (P3). Fractional greedy curvature. The relevant multilinear curvature is not c_{F} (which can be +\infty by Proposition 7 ) but its trajectory-restricted analogue, mirroring the discrete greedy curvature c_{g} of Definition 2 . Definition 5 (Fractional greedy curvature along a trajectory; restated from Definition 4 ) . Let F be the multilinear extension of a submodular f and let \mathcal{O}=\argmax_{B\in\mathcal{I}}f(B) denote the set of optimal feasible sets. For the sequence of iterates \tilde{S}_{0},\dots,\tilde{S}_{T-1}\in P produced by \textsc{DMCG-P}(F,P,T) , the fractional greedy curvature is c_{g}^{F}\;=\;1\;-\;\min_{O^{*}\in\mathcal{O}}\;\min_{\begin{subarray}{c}0\leq i0\end{subarray}}\;\frac{F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\mathbf{1}_{O^{*}})}{F(\tilde{S}_{i}-\tilde{S}_{i}\land\mathbf{1}_{O^{*}})}. Remark 5 (Finiteness on DMCG-P trajectories) . Definition 5 restricts the minimisation to the T trajectory points \{\tilde{S}_{i}\}_{i=0}^{T-1} , not the whole cube, and only positive-denominator pairs are admissible in the inner minimum. Lemma 5 ensures that active coordinates have strictly positive multilinear slope after pruning, which is the structural reason the algorithm avoids the particular concentration witnesses used to prove c_{F}=\infty in Proposition 7 . The theorem below therefore keeps c_{g}^{F}<\infty as an explicit trajectory hypothesis. In applications one proves this hypothesis, or upper-bounds c_{g}^{F} , using a certificate such as Proposition 9 . Per-step descent lemma. Lemma 6 (Per-step descent) . Let f be submodular on P (not necessarily monotone or non-negative), fix O^{*}\in\mathcal{O} , and let c_{g}^{F}\in[0,\infty) be a finite fractional greedy curvature value from Definition 5 . Put \bar{c}_{g}^{F}=\max\{1,c_{g}^{F}\} . Then for every i\in\{0,\dots,T-1\} , F(\tilde{S}_{i+1})-F(\tilde{S}_{i})\;\geq\;\tfrac{1}{T}\bigl[\,F(\mathbf{1}_{O^{*}})\;-\;\bar{c}_{g}^{F}\,F(\tilde{S}_{i})\,\bigr]\;-\;\tfrac{1}{T^{2}}\,E_{i}, (4) where the per-step discretisation error satisfies 0\leq E_{i}\leq n(n-1)\,C_{F} and \sum_{i=0}^{T-1}(1/T^{2})E_{i}\leq n(n-1)C_{F}/T . Proof. We mirror the five-line discrete proof of Theorem 1 , with each step justified by the multilinear analogue. Throughout, write v_{i}\in P for the LP maximiser selected on Line 2 ; by construction v_{i}=\mathbf{1}_{B_{i}} for some feasible set B_{i}\in\mathcal{I} , and we use this integral representation in Steps 2–3. Step 1 (pruning). By Lemma 4 , F(\tilde{S}_{i+1})\geq F(S_{i+1})=F(\tilde{S}_{i}+(1/T)\,v_{i}) . Step 2 (concavity, right-endpoint tangent). By (P2) applied with \mathbf{x}=\tilde{S}_{i} , \mathbf{d}=(1/T)\,v_{i} (both endpoints in [0,1]^{\mathcal{N}} by Lemma 3 ): F\bigl(\tilde{S}_{i}+\tfrac{1}{T}\,v_{i}\bigr)-F(\tilde{S}_{i})\;\geq\;\tfrac{1}{T}\,\langle\nabla F(S_{i+1}),\,v_{i}\rangle. Step 3 (left-to-right gradient substitution). Define the per-step discretisation error E_{i}\;\triangleq\;T\!\sum_{j\in B_{i}}\bigl[\partial_{j}F(\tilde{S}_{i})-\partial_{j}F(S_{i+1})\bigr]. (5) Since v_{i}=\mathbf{1}_{B_{i}} , this gives the exact identity \langle\nabla F(S_{i+1}),\,v_{i}\rangle\;=\;\sum_{j\in B_{i}}\partial_{j}F(S_{i+1})\;=\;\sum_{j\in B_{i}}\partial_{j}F(\tilde{S}_{i})\;-\;\tfrac{1}{T}E_{i}\;=\;\langle\nabla F(\tilde{S}_{i}),\,v_{i}\rangle\;-\;\tfrac{1}{T}E_{i}. (6) Non-negativity E_{i}\geq 0 holds because submodularity ( \partial_{j\ell}F\leq 0 for j\neq\ell ) makes each \partial_{j}F non-increasing in every other coordinate, so \partial_{j}F(S_{i+1})\leq\partial_{j}F(\tilde{S}_{i}) for every j\in B_{i} . For the upper bound, write S_{i+1}=\tilde{S}_{i}+(1/T)\mathbf{1}_{B_{i}} and apply the mean-value theorem coordinate-by-coordinate: \partial_{j}F(\tilde{S}_{i})-\partial_{j}F(S_{i+1})\;=\;-\sum_{\ell\in B_{i}\setminus j}\frac{1}{T}\,\partial_{j\ell}F(\xi_{j\ell})\;\leq\;\frac{|B_{i}|-1}{T}\,C_{F}, where \xi_{j\ell} lies on the segment [\tilde{S}_{i},S_{i+1}] and C_{F}\triangleq\max_{j\neq\ell,\,\mathbf{x}\in[0,1]^{\mathcal{N}}}|\partial_{j\ell}F(\mathbf{x})| is finite for any set function on \mathcal{N} . Multiplying by T and summing over j\in B_{i} : E_{i}\;\leq\;|B_{i}|(|B_{i}|-1)\,C_{F}\;\leq\;n(n-1)\,C_{F}. Since |B_{i}|\leq n , the total discretisation error is \sum_{i=0}^{T-1}(1/T^{2})\,E_{i}\leq n(n-1)\,C_{F}/T . Step 4 (linear selection, unweighted). Since Line 2 picks v_{i} to maximise \langle\nabla F(\tilde{S}_{i}),\,x\rangle over all x\in P and \mathbf{1}_{O^{*}}\in P (as O^{*}\in\mathcal{O}\subseteq\mathcal{I} ), \langle\nabla F(\tilde{S}_{i}),\,v_{i}\rangle\;\geq\;\langle\nabla F(\tilde{S}_{i}),\,\mathbf{1}_{O^{*}}\rangle\;=\;\sum_{j\in O^{*}}\partial_{j}F(\tilde{S}_{i}). This is a direct consequence of LP optimality and does not require matroid structure. Step 5 (submodular union bound, with slope monotonicity). By (P3) applied with \mathbf{y}=\mathbf{1}_{O^{*}} : F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\tilde{S}_{i})\;\leq\;\sum_{j\in O^{*}}(1-(\tilde{S}_{i})_{j})\,\partial_{j}F(\tilde{S}_{i})\;\leq\;\sum_{j\in O^{*}}\partial_{j}F(\tilde{S}_{i}), where the second inequality uses (\tilde{S}_{i})_{j}\in[0,1] together with Lemma 5 , which guarantees \partial_{j}F(\tilde{S}_{i})\geq 0 whenever (\tilde{S}_{i})_{j}>0 (and trivially whenever (\tilde{S}_{i})_{j}=0 then 1-(\tilde{S}_{i})_{j}=1 ). Combining Steps 4 and 5: \langle\nabla F(\tilde{S}_{i}),\,v_{i}\rangle\;\geq\;F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\tilde{S}_{i}). (7) Step 6 (fractional curvature). Let \mathbf{w}_{i}\;\triangleq\;\tilde{S}_{i}-\tilde{S}_{i}\land\mathbf{1}_{O^{*}}. If \mathbf{w}_{i}=0 , then \tilde{S}_{i}\lor\mathbf{1}_{O^{*}}=\mathbf{1}_{O^{*}} and the displayed inequality below is an equality. Otherwise, every coordinate in \operatorname{supp}(\mathbf{w}_{i}) is active in \tilde{S}_{i} , so Lemma 5 gives \partial_{j}F(\tilde{S}_{i})>0 for each j\in\operatorname{supp}(\mathbf{w}_{i}) . Since t\mathbf{w}_{i}\leq\tilde{S}_{i} for t\in[0,1] , submodularity of the multilinear extension gives \partial_{j}F(t\mathbf{w}_{i})\geq\partial_{j}F(\tilde{S}_{i})>0 on this support. With F(\mathbf{0})=0 , F(\mathbf{w}_{i})=\int_{0}^{1}\langle\nabla F(t\mathbf{w}_{i}),\mathbf{w}_{i}\rangle\,dt>0. Thus, in the nonzero case, the present pair appears in Definition 5 . Since \bar{c}_{g}^{F}\geq c_{g}^{F} , the curvature inequality is also valid with \bar{c}_{g}^{F} in place of c_{g}^{F} ; in the zero case, the same display holds trivially. Hence F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\mathbf{1}_{O^{*}})\;\geq\;(1-\bar{c}_{g}^{F})\,F(\mathbf{w}_{i}), so F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\tilde{S}_{i})\;\geq\;F(\mathbf{1}_{O^{*}})+(1-\bar{c}_{g}^{F})\,F(\tilde{S}_{i}-\tilde{S}_{i}\land\mathbf{1}_{O^{*}})-F(\tilde{S}_{i}). Step 7 (zeroing the O^{*} -coordinates of \tilde{S}_{i} only decreases F ). The vector \tilde{S}_{i}-\tilde{S}_{i}\land\mathbf{1}_{O^{*}} is obtained from \tilde{S}_{i} by zeroing every coordinate j\in O^{*} . Fix any order for this sequential zeroing. When coordinate j is reached, all other changes made so far have only decreased coordinates. By submodularity of the multilinear extension, decreasing other coordinates can only increase the remaining slope \partial_{j}F ; hence Lemma 5 implies that either the current value of coordinate j is zero, or the current slope in direction j is still nonnegative. Multilinearity in coordinate j therefore implies that zeroing j changes F by -(\text{current }j\text{-mass})\,\partial_{j}F(\cdot)\leq 0 . Iterating over j\in O^{*} gives F(\tilde{S}_{i}-\tilde{S}_{i}\land\mathbf{1}_{O^{*}})\;\leq\;F(\tilde{S}_{i}). Substituting this into the previous display and expanding (1-\bar{c}_{g}^{F}) : F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\tilde{S}_{i})\;\geq\;F(\mathbf{1}_{O^{*}})\;-\;\bar{c}_{g}^{F}\,F(\tilde{S}_{i}). Assembly. Chaining Steps 1–3, 4–5 (as ( 7 )), and 6–7: \displaystyle F(\tilde{S}_{i+1})-F(\tilde{S}_{i}) \displaystyle\geq\;\tfrac{1}{T}\,\langle\nabla F(S_{i+1}),\,v_{i}\rangle (Steps 1–2) \displaystyle\geq\;\tfrac{1}{T}\,\langle\nabla F(\tilde{S}_{i}),\,v_{i}\rangle\;-\;\tfrac{1}{T^{2}}E_{i} (Step 3) \displaystyle\geq\;\tfrac{1}{T}\bigl[F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\tilde{S}_{i})\bigr]\;-\;\tfrac{1}{T^{2}}E_{i} (Steps 4–5) \displaystyle\geq\;\tfrac{1}{T}\bigl[F(\mathbf{1}_{O^{*}})-\bar{c}_{g}^{F}\,F(\tilde{S}_{i})\bigr]\;-\;\tfrac{1}{T^{2}}E_{i} \displaystyle\text{(Steps 6--7)}. This is ( 4 ). Finally, \sum_{i=0}^{T-1}(1/T^{2})E_{i}\leq n(n-1)\,C_{F}/T by the bound on E_{i} from ( 5 ); hence the aggregate discretisation error is O(1/T) and vanishes as T\to\infty . ∎ Remark 6 (On the discretisation error) . It is tempting to claim that the per-step equality F\bigl(\tilde{S}_{i}+\tfrac{1}{T}\,v_{i}\bigr)-F(\tilde{S}_{i})\;=\;\tfrac{1}{T}\,\langle\nabla F(\tilde{S}_{i}),\,v_{i}\rangle holds exactly, “because F is multilinear.” This is false in general: multilinearity makes F linear in each coordinate separately , but along a direction v_{i} with multiple non-zero entries, t\mapsto F(\mathbf{x}+t\,v_{i}) is a polynomial of degree up to |\operatorname{supp}(v_{i})| in t , with quadratic coefficients \partial_{j\ell}F\leq 0 (submodularity) and bounded higher-order cross-terms. The cleanest exact statement is (P2): the secant slope exceeds the right-endpoint gradient slope, so F(\mathbf{x}+t\,v)-F(\mathbf{x})\geq t\,\langle\nabla F(\mathbf{x}+t\,v),\,v\rangle . Replacing the right-endpoint gradient with the left-endpoint one costs O(t)=O(1/T) per step via ( 6 ), which sums to O(1/T) total—vanishing in the limit but not zero at finite T . The T\to\infty bound is unaffected; the finite- T bound carries this additive O(1/T) penalty. Theorem 7 (General DMCG-P guarantee) . Let \mathcal{I}\subseteq 2^{\mathcal{N}} be downward-closed, let P=\operatorname{conv}\{\mathbf{1}_{B}:B\in\mathcal{I}\} , and assume exact linear optimization over \mathcal{I} . Let f:2^{\mathcal{N}}\to\mathbb{R} be submodular (not necessarily monotone or non-negative) and let O^{*}\in\argmax_{B\in\mathcal{I}}f(B) . Let n=|\mathcal{N}| , and let c_{g}^{F}\in[0,\infty) be a finite fractional greedy curvature value for the trajectory of \textsc{DMCG-P}(F,P,T) from Definition 5 . Put \bar{c}_{g}^{F}=\max\{1,c_{g}^{F}\} . If \bar{c}_{g}^{F}\leq T (equivalently \delta\bar{c}_{g}^{F}\leq 1 for \delta=1/T ), then the output \tilde{S}_{T} satisfies F(\tilde{S}_{T})\;\geq\;\frac{1-(1-\bar{c}_{g}^{F}/T)^{T}}{\bar{c}_{g}^{F}}\,f(O^{*})\;-\;\frac{n(n-1)\,C_{F}}{T}\;\xrightarrow[T\to\infty]{}\;\frac{1-e^{-\bar{c}_{g}^{F}}}{\bar{c}_{g}^{F}}\,f(O^{*}). The step count T is independent of the cardinality or matroid-rank constraint; choosing T large reduces the discretization error at the cost of O(Tn) oracle calls. The sharper small-curvature formula is recovered in the monotone setting by the classical analysis. Proof. Let a_{i}\triangleq F(\tilde{S}_{i}) , A\triangleq F(\mathbf{1}_{O^{*}})=f(O^{*}) , put \bar{c}_{g}^{F}=\max\{1,c_{g}^{F}\} , and let \delta_{i}\triangleq(1/T^{2})E_{i} from Lemma 6 . Equation ( 4 ) (which holds for arbitrary submodular f , without monotonicity) gives the linear recurrence a_{i+1}\;\geq\;\tfrac{1}{T}A\;+\;\bigl(1-\bar{c}_{g}^{F}/T\bigr)\,a_{i}\;-\;\delta_{i},\qquad a_{0}=0. Because \bar{c}_{g}^{F}\leq T , the recurrence coefficient 1-\bar{c}_{g}^{F}/T\geq 0 . Iterating: a_{T}\;\geq\;\tfrac{A}{T}\sum_{i=0}^{T-1}\bigl(1-\bar{c}_{g}^{F}/T\bigr)^{i}\;-\;\sum_{i=0}^{T-1}\bigl(1-\bar{c}_{g}^{F}/T\bigr)^{T-1-i}\,\delta_{i}. The geometric sum evaluates to \tfrac{A}{T}\cdot\tfrac{1-(1-\bar{c}_{g}^{F}/T)^{T}}{\bar{c}_{g}^{F}/T}=\tfrac{A}{\bar{c}_{g}^{F}}\bigl(1-(1-\bar{c}_{g}^{F}/T)^{T}\bigr) , and each factor (1-\bar{c}_{g}^{F}/T)^{T-1-i}\in[0,1] (since \bar{c}_{g}^{F}/T\in[0,1] ), so the error term is bounded by \sum_{i}\delta_{i}=O(1/T) . This gives the stated finite- T bound with \sum_{i}\delta_{i}\leq n(n-1)\,C_{F}/T . Sending T\to\infty for fixed finite \bar{c}_{g}^{F} , (1-\bar{c}_{g}^{F}/T)^{T}\to e^{-\bar{c}_{g}^{F}} by the elementary exponential limit, the error vanishes, and the limit is (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F}\cdot f(O^{*}) . ∎ Remark 7 (Reduction to classical CC curvature) . When f is monotone submodular (so c_{g}^{F}\leq c_{F}=c_{f}=\alpha_{g}\in[0,1] by Theorem 3 (a), with \alpha_{g} the classical Conforti–Cornuéjols curvature), the classical continuous-greedy analysis yields F(\tilde{S}_{T})\geq(1-e^{-\alpha_{g}})/\alpha_{g}\cdot f(O^{*}) in the limit T\to\infty . The non-monotone DMCG-P recurrence above uses \bar{c}_{g}^{F}=\max\{1,c_{g}^{F}\} ; the sharper small-curvature formula comes from monotonicity, not from Step 7 of the non-monotone proof. When f takes negative values, c_{F}=\infty globally by Proposition 7 ; Theorem 7 still applies whenever its finite trajectory-curvature hypothesis is verified. For decomposable objectives, § H.4 supplies a closed-form certificate for that hypothesis. Why this works for unweighted greedy. The unweighted selection rule is sufficient because the proof needs an upper bound on the union gain, not a lower bound on a weighted gradient. (P3) gives F(\tilde{S}_{i}\lor\mathbf{1}_{O^{*}})-F(\tilde{S}_{i})\leq\sum_{j\in O^{*}}(1-(\tilde{S}_{i})_{j})\partial_{j}F(\tilde{S}_{i}) , and the analysis then upper-bounds this weighted sum by the unweighted sum \sum_{j\in O^{*}}\partial_{j}F(\tilde{S}_{i})=\langle\nabla F(\tilde{S}_{i}),\,\mathbf{1}_{O^{*}}\rangle . The latter is free when \partial_{j}F(\tilde{S}_{i})\geq 0 for every j\in O^{*} —which is exactly what Lemma 5 plus the O^{*}\subseteq\mathcal{N} case analysis in Step 5 of the proof provides (coordinates j\in O^{*} with (\tilde{S}_{i})_{j}=0 have 1-(\tilde{S}_{i})_{j}=1 trivially; coordinates with (\tilde{S}_{i})_{j}>0 have \partial_{j}F\geq 0 by Lemma 5 , so (1-(\tilde{S}_{i})_{j})\partial_{j}F\leq\partial_{j}F regardless). Thus unweighted DMCG-P—the feasible-set form B_{i}\in\arg\max_{B\in\mathcal{I}}\sum_{j\in B}\partial_{j}F(\tilde{S}_{i}) with v_{i}=\mathbf{1}_{B_{i}} —is the correct clean algorithm and the discrete proof lifts directly. H.4 Decomposable Certificate for c_{g}^{F} Theorem 7 delivers the headline DMCG-P guarantee (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F}\cdot f(O^{*}) conditional on c_{g}^{F}<\infty and \delta\bar{c}_{g}^{F}\leq 1 . Lemma 5 provides the positive-slope invariant used in the proof, but the theorem is most useful when c_{g}^{F} can be bounded in closed form. This subsection provides such a bound for the decomposable case f=g-\ell , mirroring the discrete removal-marginal certificate c_{g}\leq\alpha_{g}/(1-\hat{r}) of Proposition 4 . The content here is a computational certificate for c_{g}^{F} , not a separate approximation guarantee: plugging the certificate into Theorem 7 recovers the (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F} bound for negative-valued f . We first fix the setting (§ H.4.1 ), then prove the multilinear lift of the CC-curvature inequality that the analysis requires (§ H.4.2 ), state the OPT-aware comparison bound (§ H.4.3 ), obtain the OPT-free certificate c_{g}^{F}\leq\alpha_{g}/(1-\hat{r}_{F}) from the pruned trajectory (§ H.4.4 ), and assemble the decomposable-certificate proposition (§ H.4.5 ). H.4.1 Setting Throughout this subsection, f=g-\ell where • g:2^{\mathcal{N}}\to\mathbb{R}_{\geq 0} is monotone submodular with Conforti–Cornuéjols curvature \alpha_{g}\in[0,1] , characterised (Definition 1 and equation ( 1 )) by g(X\cup Y)-g(Y)\;\geq\;(1-\alpha_{g})\,g(X\setminus Y)\qquad\forall\,X,Y\subseteq\mathcal{N}; (8) • \ell:2^{\mathcal{N}}\to\mathbb{R}_{\geq 0} is non-negative modular with per-element costs \ell_{j}\triangleq\ell(\{j\}) , so \ell(A)=\sum_{j\in A}\ell_{j} for every A\subseteq\mathcal{N} . The multilinear extensions decompose as F=G-L , with G the multilinear extension of g (monotone submodular) and L(\mathbf{x})\;=\;\sum_{j\in\mathcal{N}}\ell_{j}x_{j} (9) exactly linear in \mathbf{x} . Note that f itself may take negative values, so c_{F}=\infty by Proposition 7 ; the analysis below operates entirely through the trajectory-restricted curvature c_{g}^{F} of Definition 5 , which is bounded by the decomposable certificates proved below. H.4.2 Multilinear CC-curvature inequality for G The multilinear extension G of a monotone submodular g with CC curvature \alpha_{g} inherits a fractional form of the set inequality ( 8 ). We state and prove the precise form required for the decomposable analysis. Related multilinear inequalities are standard (e.g. [ 5 ] ), but the statement below—comparing G(\mathbf{x}\lor\mathbf{y}) with G(\mathbf{x}-\mathbf{x}\land\mathbf{y}) —does not seem to appear in this form in the literature, so we include a self-contained proof. Lemma 7 (Multilinear CC-curvature inequality, elementwise form) . Let g:2^{\mathcal{N}}\to\mathbb{R}_{\geq 0} be monotone submodular with CC curvature \alpha_{g}\in[0,1] , and let G be its multilinear extension. For all \mathbf{x},\mathbf{y}\in[0,1]^{\mathcal{N}} , writing \mathbf{w}\triangleq\mathbf{x}-\mathbf{x}\land\mathbf{y} (so w_{j}=(x_{j}-y_{j})_{+} ), G(\mathbf{x}\lor\mathbf{y})-G(\mathbf{y})\;\geq\;(1-\alpha_{g})\sum_{j\in\mathcal{N}}w_{j}\,g(\{j\}). (10) In particular, by g -subadditivity G(\mathbf{w})\leq\sum_{j}w_{j}\,g(\{j\}) , the weaker set-style inequality G(\mathbf{x}\lor\mathbf{y})-G(\mathbf{y})\;\geq\;(1-\alpha_{g})\,G(\mathbf{w}) (11) follows by combining the elementwise bound with subadditivity. Proof. The elementwise bound ( 10 ) follows from the pointwise gradient inequality \partial_{j}G(\mathbf{z})\;\geq\;(1-\alpha_{g})\,g(\{j\})\qquad\text{for every }\mathbf{z}\in[0,1]^{\mathcal{N}}\text{ and every }j\in\mathcal{N}, (12) integrated along the straight-line interpolation from \mathbf{y} to \mathbf{x}\lor\mathbf{y} . Step 1 (pointwise gradient lower bound). Submodularity of g is equivalent to the mixed-partial condition \partial_{j\ell}G\leq 0 for \ell\neq j , i.e. \partial_{j}G is coordinate-wise non-increasing in every other coordinate. Hence for any \mathbf{z}\in[0,1]^{\mathcal{N}} , \partial_{j}G(\mathbf{z})\;\geq\;\partial_{j}G(\mathbf{1}_{\mathcal{N}})\;=\;g(\mathcal{N})-g(\mathcal{N}\setminus\{j\})\;\geq\;(1-\alpha_{g})\,g(\{j\}), where the final inequality is the CC-curvature definition \alpha_{g}=1-\min_{e,S\not\ni e}\Delta_{g}(e\mid S)/g(\{e\}) specialised to S=\mathcal{N}\setminus\{j\} . This gives ( 12 ) (normalisation of g is not needed). Step 2 (telescoping via multilinearity). Order \mathcal{N}=\{1,\dots,n\} arbitrarily and interpolate from \mathbf{y} to \mathbf{x}\lor\mathbf{y} one coordinate at a time: set \mathbf{z}^{(0)}=\mathbf{y} and \mathbf{z}^{(j)}=\mathbf{z}^{(j-1)}+w_{j}\,\mathbf{e}_{j} , so \mathbf{z}^{(n)}=\mathbf{y}+\mathbf{w}=\mathbf{x}\lor\mathbf{y} (using \max(x_{j},y_{j})=y_{j}+(x_{j}-y_{j})_{+} ). By multilinearity of G in each coordinate separately, G(\mathbf{z}^{(j)})-G(\mathbf{z}^{(j-1)})\;=\;w_{j}\,\partial_{j}G(\mathbf{z}^{(j-1)}), and summing, G(\mathbf{x}\lor\mathbf{y})-G(\mathbf{y})\;=\;\sum_{j=1}^{n}w_{j}\,\partial_{j}G(\mathbf{z}^{(j-1)}). (13) Applying ( 12 ) at each \mathbf{z}^{(j-1)}\in[0,1]^{\mathcal{N}} gives ( 10 ). Step 3 (set-style corollary). By g\geq 0 and submodularity, g is subadditive: g(A)\leq\sum_{e\in A}g(\{e\}) . Taking expectations under R\sim\mathbf{w} (coordinate-wise independent Bernoullis), G(\mathbf{w})=\mathbb{E}[g(R)]\leq\mathbb{E}\bigl[\sum_{j\in R}g(\{j\})\bigr]=\sum_{j}w_{j}\,g(\{j\}) . Combining with ( 10 ) yields ( 11 ). ∎ Remark 8 (Strength of the elementwise form) . The elementwise inequality ( 10 ) is strictly stronger than the set-style form ( 11 ), since the subadditivity step G(\mathbf{w})\leq\sum_{j}w_{j}\,g(\{j\}) can be strict. Both forms are used downstream: ( 11 ) is the clean multilinear analogue of ( 8 ), while ( 10 ) is what drives the fractional OPT-free certificate in § H.4.4 . H.4.3 OPT-aware decomposable bound For each iterate write \mathbf{w}_{i}\;\triangleq\;\tilde{S}_{i}-\tilde{S}_{i}\land\mathbf{1}_{O^{*}}\qquad\text{(coordinate $j$: $(\mathbf{w}_{i})_{j}=(\tilde{S}_{i})_{j}\,\mathbf{1}[j\notin O^{*}]$),} (14) the “outside-OPT” fractional mass. Since O^{*} is a set and \mathbf{1}_{O^{*}} is \{0,1\} -valued, \tilde{S}_{i}\land\mathbf{1}_{O^{*}} zeros out the coordinates j\in\mathcal{N}\setminus O^{*} , so \mathbf{w}_{i}=\tilde{S}_{i}\odot\mathbf{1}[\cdot\notin O^{*}] is literally \tilde{S}_{i} restricted to \mathcal{N}\setminus O^{*} . Define the trajectory-level cost ratio \rho_{F}\;\triangleq\;\max_{\begin{subarray}{c}O^{*}\in\mathcal{O}\\ 0\leq i0\end{subarray}}\,\frac{L(\mathbf{w}_{i})}{G(\mathbf{w}_{i})}. (15) (If G(\mathbf{w}_{i})=0 for every i,O^{*} , set \rho_{F}=0 ; the curvature definition then does not involve any active constraint from the decomposable side.) Proposition 8 (OPT-aware fractional curvature bound) . Let f=g-\ell be decomposable as in § H.4.1 , and consider the trajectory of \textsc{DMCG-P}(F,P,T) . If \rho_{F}<1 , then the fractional greedy curvature of Definition 5 satisfies c_{g}^{F}\;\leq\;\frac{\alpha_{g}}{1-\rho_{F}}. (16) Proof. Fix O^{*}\in\mathcal{O} and i\in\{0,\dots,T-1\} with F(\mathbf{w}_{i})>0 (the only indices active in Definition 5 ); write \mathbf{x}=\tilde{S}_{i} and \mathbf{y}=\mathbf{1}_{O^{*}} , so \mathbf{w}_{i}=\mathbf{x}-\mathbf{x}\land\mathbf{y} . Decompose F=G-L and expand the numerator of the curvature ratio: \displaystyle F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{y}) \displaystyle\;=\;\bigl[\,G(\mathbf{x}\lor\mathbf{y})-G(\mathbf{y})\,\bigr]\;-\;\bigl[\,L(\mathbf{x}\lor\mathbf{y})-L(\mathbf{y})\,\bigr] \displaystyle\;\geq\;(1-\alpha_{g})\,G(\mathbf{w}_{i})\;-\;\bigl[\,L(\mathbf{x}\lor\mathbf{y})-L(\mathbf{y})\,\bigr] by Lemma 7 . For the L side, linearity of L gives L(\mathbf{x}\lor\mathbf{y})+L(\mathbf{x}\land\mathbf{y})=L(\mathbf{x})+L(\mathbf{y}) (coordinate-wise: \max(x_{j},y_{j})+\min(x_{j},y_{j})=x_{j}+y_{j} ), so L(\mathbf{x}\lor\mathbf{y})-L(\mathbf{y})\;=\;L(\mathbf{x})-L(\mathbf{x}\land\mathbf{y})\;=\;L(\mathbf{x}-\mathbf{x}\land\mathbf{y})\;=\;L(\mathbf{w}_{i}). (17) Let \rho_{i}\triangleq L(\mathbf{w}_{i})/G(\mathbf{w}_{i}) (finite by G(\mathbf{w}_{i})>0 , since F(\mathbf{w}_{i})>0 and L\geq 0 together imply G(\mathbf{w}_{i})>0 ). Then F(\mathbf{w}_{i})=G(\mathbf{w}_{i})-L(\mathbf{w}_{i})=(1-\rho_{i})\,G(\mathbf{w}_{i}) , and F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{y})\;\geq\;\bigl[(1-\alpha_{g})-\rho_{i}\bigr]\,G(\mathbf{w}_{i}). Dividing by F(\mathbf{w}_{i})=(1-\rho_{i})\,G(\mathbf{w}_{i})>0 , \frac{F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{y})}{F(\mathbf{w}_{i})}\;\geq\;\frac{(1-\alpha_{g})-\rho_{i}}{1-\rho_{i}}\;=\;1-\frac{\alpha_{g}}{1-\rho_{i}}\;\geq\;1-\frac{\alpha_{g}}{1-\rho_{F}}, (18) using \rho_{i}\leq\rho_{F}<1 and monotonicity of t\mapsto\alpha_{g}/(1-t) on [0,1) . Taking the infimum over i and O^{*}\in\mathcal{O} and applying Definition 5 gives c_{g}^{F}\leq\alpha_{g}/(1-\rho_{F}) . ∎ H.4.4 OPT-free fractional certificate Proposition 8 bounds c_{g}^{F} in terms of the OPT-dependent vectors \mathbf{w}_{i} . For a deployable certificate we want an OPT-free quantity computed directly from the DMCG-P trajectory. The right fractional analogue of the discrete removal marginal \Delta_{g}(e\mid A_{i}\setminus\{e\}) is the current multilinear slope \partial_{j}G(\tilde{S}_{i}) . Define the removal-slope ratio \hat{r}_{F}\;\triangleq\;\max_{\begin{subarray}{c}0\leq i0\end{subarray}}\frac{\ell_{j}}{\partial_{j}G(\tilde{S}_{i})}, (19) with value 0 if the index set is empty. Lemma 5 gives \partial_{j}F(\tilde{S}_{i})=\partial_{j}G(\tilde{S}_{i})-\ell_{j}>0 on every active coordinate, so every denominator in ( 19 ) is positive and \hat{r}_{F}<1 . Lemma 8 (Removal-slope domination) . Let \mathbf{x}=\tilde{S}_{i} be a DMCG-P iterate and let \mathbf{w}\in[0,1]^{\mathcal{N}} satisfy 0\leq\mathbf{w}\leq\mathbf{x} coordinate-wise and \operatorname{supp}(\mathbf{w})\subseteq\operatorname{supp}(\mathbf{x}) . Then L(\mathbf{w})\;\leq\;\hat{r}_{F}\,G(\mathbf{w}). Proof. By definition of \hat{r}_{F} , for every coordinate with w_{j}>0 , \ell_{j}\leq\hat{r}_{F}\,\partial_{j}G(\mathbf{x}) . Hence L(\mathbf{w})=\sum_{j}w_{j}\ell_{j}\;\leq\;\hat{r}_{F}\sum_{j}w_{j}\partial_{j}G(\mathbf{x}). It remains to compare the weighted slope sum with G(\mathbf{w}) . Since G is the multilinear extension of a monotone submodular function, it is DR-submodular: each partial derivative is coordinate-wise non-increasing. For t\in[0,1] , we have t\mathbf{w}\leq\mathbf{w}\leq\mathbf{x} , so \partial_{j}G(t\mathbf{w})\geq\partial_{j}G(\mathbf{x}) . Using normalization G(\mathbf{0})=0 and integrating along the ray t\mathbf{w} , G(\mathbf{w})=\int_{0}^{1}\langle\nabla G(t\mathbf{w}),\mathbf{w}\rangle\,dt\;\geq\;\sum_{j}w_{j}\partial_{j}G(\mathbf{x}). Combining the two displays gives the claim. ∎ Theorem 8 (OPT-free fractional curvature certificate) . Let f=g-\ell be decomposable as in § H.4.1 and consider the trajectory of \textsc{DMCG-P}(F,P,T) . The fractional greedy curvature of Definition 5 satisfies c_{g}^{F}\;\leq\;\frac{\alpha_{g}}{1-\hat{r}_{F}}. (20) Proof. Fix O^{*}\in\mathcal{O} and i\in\{0,\dots,T-1\} with F(\mathbf{w}_{i})>0 , and write \mathbf{x}=\tilde{S}_{i} , \mathbf{y}=\mathbf{1}_{O^{*}} , so \mathbf{w}_{i}=\mathbf{x}-\mathbf{x}\land\mathbf{y} . Since 0\leq\mathbf{w}_{i}\leq\mathbf{x} and \operatorname{supp}(\mathbf{w}_{i})\subseteq\operatorname{supp}(\mathbf{x}) , Lemma 8 gives L(\mathbf{w}_{i})\leq\hat{r}_{F}\,G(\mathbf{w}_{i}). (21) The set-style multilinear CC inequality ( 11 ) applied to \mathbf{x},\mathbf{y} gives G(\mathbf{x}\lor\mathbf{y})-G(\mathbf{y})\;\geq\;(1-\alpha_{g})G(\mathbf{w}_{i}), (22) and modularity of \ell (as in ( 17 )) gives L(\mathbf{x}\lor\mathbf{y})-L(\mathbf{y})=L(\mathbf{w}_{i}) . Let \tau\triangleq L(\mathbf{w}_{i})/G(\mathbf{w}_{i}) . The positive-denominator assumption F(\mathbf{w}_{i})>0 implies \tau<1 , and ( 21 ) implies 0\leq\tau\leq\hat{r}_{F} . Then \displaystyle F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{y}) \displaystyle\;=\;\bigl[G(\mathbf{x}\lor\mathbf{y})-G(\mathbf{y})\bigr]-L(\mathbf{w}_{i}) \displaystyle\;\geq\;(1-\alpha_{g})\,G(\mathbf{w}_{i})-L(\mathbf{w}_{i})\;=\;\bigl[(1-\alpha_{g})-\tau\bigr]\,G(\mathbf{w}_{i}), while F(\mathbf{w}_{i})=G(\mathbf{w}_{i})-L(\mathbf{w}_{i})=(1-\tau)G(\mathbf{w}_{i}) . Dividing, \frac{F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{y})}{F(\mathbf{w}_{i})}\;\geq\;\frac{(1-\alpha_{g})-\tau}{1-\tau}. The right-hand side is decreasing in \tau , since its derivative is -\alpha_{g}/(1-\tau)^{2} . Because \tau\leq\hat{r}_{F} , \frac{F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{y})}{F(\mathbf{w}_{i})}\;\geq\;1-\frac{\alpha_{g}}{1-\hat{r}_{F}}. Taking the infimum over i and O^{*}\in\mathcal{O} and applying Definition 5 yields ( 20 ). ∎ Remark 9 (Relationship to the discrete certificate) . Theorem 8 is the exact multilinear analogue of the discrete removal-marginal certificate for decomposable objectives. In the discrete-greedy limit ( \tilde{S}_{i}\to\mathbf{1}_{A_{i}} integer-valued), \partial_{j}G(\tilde{S}_{i}) reduces to \Delta_{g}(j\mid A_{i}\setminus\{j\}) , and ( 20 ) reduces to c_{g}\leq\alpha_{g}/(1-\hat{r}) . Remark 10 (Verifiability of \hat{r}_{F} ) . The certificate is computed after the run from the active coordinates and the component gradients \partial_{j}G(\tilde{S}_{i}) . No optimum is needed. The curvature parameter \alpha_{g} admits closed-form expressions for the application classes in this paper (Appendix D ). When \alpha_{g} is not known analytically, the total curvature \alpha_{g}^{\mathrm{total}}=1-\min_{e}\,\Delta_{g}(e\mid N\setminus\{e\})/g(\{e\}) is a computable upper bound that can be substituted for \alpha_{g} . H.4.5 Decomposable certificate proposition Combining Theorem 8 with the headline Theorem 7 yields the main deployable result of this section. Proposition 8 remains a sharper OPT-aware comparison when the optimum is available. Proposition 9 (Decomposable certificate for c_{g}^{F} ) . Let f=g-\ell be decomposable as in § H.4.1 , let O^{*}\in\mathcal{O} , and consider the trajectory of \textsc{DMCG-P}(F,P,T) . Then the OPT-free certificate c_{g}^{F}\leq\frac{\alpha_{g}}{1-\hat{r}_{F}} holds, with \hat{r}_{F}<1 computed from ( 19 ). Plugging this certificate into Theorem 7 and using monotonicity of c\mapsto(1-e^{-c})/c on c>0 yields the approximation bound F(\tilde{S}_{T})\;\geq\;\frac{1-(1-\bar{c}_{g}^{F}/T)^{T}}{\bar{c}_{g}^{F}}\,f(O^{*})\;-\;O(1/T)\;\xrightarrow[T\to\infty]{}\;\frac{1-e^{-\bar{c}_{g}^{F}}}{\bar{c}_{g}^{F}}\,f(O^{*}), (23) and in particular F(\tilde{S}_{T})\;\geq\;\frac{1-e^{-\bar{c}_{\mathrm{cert}}}}{\bar{c}_{\mathrm{cert}}}\,f(O^{*})\;-\;o(1),\qquad\hat{c}_{g}^{F}\;\triangleq\;\frac{\alpha_{g}}{1-\hat{r}_{F}},\quad\bar{c}_{\mathrm{cert}}\triangleq\max\{1,\hat{c}_{g}^{F}\}. (24) No monotonicity or non-negativity of f itself is required; in particular, f may take negative values (where c_{F}=\infty globally and the classical MCG analysis fails). Proof. The curvature bound is Theorem 8 . The approximation bound ( 23 ) is Theorem 7 applied to f with c_{g}^{F} upper-bounded by this certificate. Equation ( 24 ) follows from monotonicity of c\mapsto(1-e^{-c})/c on c>0 (decreasing), so an upper bound on \bar{c}_{g}^{F} yields a lower bound on (1-e^{-\bar{c}_{g}^{F}})/\bar{c}_{g}^{F} . Finally, the hypothesis of Theorem 7 is finite trajectory curvature, made concrete here by the closed-form certificate (and by taking T in the stated discretization regime); no monotonicity of f is invoked at any step of Theorem 7 ’s proof (see Lemma 6 , which is stated and proved for arbitrary submodular f ). ∎ Remark 11 (Reductions and comparisons) . (i) Purely submodular case ( \ell\equiv 0 ). Then \rho_{F}=0 , \hat{r}_{F}=0 , and Proposition 9 gives c_{g}^{F}\leq\alpha_{g} , so the approximation bound ( 23 ) collapses to F(\tilde{S}_{T})\geq(1-e^{-\alpha_{g}})/\alpha_{g}\,f(O^{*})-o(1) , recovering both the classical CC-curvature guarantee Theorem 1 and the monotone specialisation of the headline Theorem 7 (with c_{g}^{F}\leq\alpha_{g} from Theorem 3 (a)). (ii) Negative f is allowed. No non-negativity assumption on f=g-\ell is made, and monotonicity is likewise not assumed. The relevant finiteness of c_{g}^{F} comes from the certificate \hat{r}_{F}<1 (or the sharper OPT-aware condition \rho_{F}<1 ), together with the pruning slope invariant from Lemma 5 ; plugging the certificate into Theorem 7 yields the approximation bound. (iii) Comparison to the Harshaw–Feldman–Ward–Karbasi additive bound. The additive guarantee of [ 11 ] for g-\ell (and its continuous analogue via Feldman–Naor–Schwartz) is, in multilinear form, F(\tilde{S}_{T})\geq(1-1/e)\,G(\mathbf{1}_{O^{*}})-L(\mathbf{1}_{O^{*}}) . Writing \rho^{*}\triangleq L(\mathbf{1}_{O^{*}})/G(\mathbf{1}_{O^{*}}) (the OPT-level cost ratio), this additive bound is non-vacuous only when \rho^{*}<1-1/e and collapses to 0 at \rho^{*}=1-1/e . The multiplicative bound ( 24 ) is strictly positive whenever \hat{r}_{F}<1 and f(O^{*})>0 , and in particular it can remain informative in regimes where the additive bound is vacuous. H.5 Non-Negative Non-Monotone Regime via Damped wDMCG-P The headline DMCG-P guarantee (Theorem 7 ) and the decomposable certificate (Proposition 9 ) together cover every submodular f with finite trajectory curvature c_{g}^{F} —including f that takes negative values. In this section we treat the complementary regime: non-negative submodular f with no further structure (neither monotone nor decomposable), where c_{g}^{F} need not be bounded and the goal is to recover a 1/e -type multiplicative guarantee via a measured-continuous-greedy style trajectory. The algorithm is a weighted, damped variant of DMCG-P (wDMCG-P-damped), structurally distinct from the unweighted DMCG-P of § H.1 : both the weighted LP selection and the (1-\tilde{S}_{i,j}) damping factor are new ingredients. H.5.1 Algorithm Fix step count k\in\mathbb{N} and damping step size \delta=1/k . Input: multilinear oracle F of non-negative submodular f , downward-closed solvable polytope P\subseteq[0,1]^{\mathcal{N}} with feasible-set family \mathcal{I} , step count k\in\mathbb{N} \tilde{S}_{0}\leftarrow\mathbf{0} ; \delta\leftarrow 1/k 1 for i\leftarrow 0 to k-1 do 2 // Pruning: zero every coordinate with non-positive slope. while \exists\,j\in\mathcal{N} with (\tilde{S}_{i})_{j}>0 and \partial_{j}F(\tilde{S}_{i})\leq 0 do 3 (\tilde{S}_{i})_{j}\leftarrow 0 4 // Weighted LP selection over feasible sets. B_{i}\leftarrow\arg\max_{B\in\mathcal{I}}\sum_{j\in\mathcal{N}}(1-(\tilde{S}_{i})_{j})\,\partial_{j}F(\tilde{S}_{i})\,\mathbf{1}_{B,j} 5 // Damped update: residual-room step. \tilde{S}_{i+1,j}\leftarrow\tilde{S}_{i,j}+\delta\,(1-\tilde{S}_{i,j})\,\mathbf{1}_{B_{i},j}\quad\forall j\in\mathcal{N} 6 return \tilde{S}_{k} 7 Algorithm 3 \textsc{wDMCG-P}(F,P,k) — wDMCG-P with damped update Two remarks on Algorithm 3 . (i) The pruning step is kept for algorithmic consistency with DMCG-P but plays no load-bearing role in the analysis below: the descent lemma uses only the weighted LP optimality of B_{i} and the FNS correlation-gap bound (Lemma 2.2 of [ 9 ] ), neither of which requires pruning. In the proof, \tilde{S}_{i} denotes the point after this optional pruning at the start of iteration i ; pruning can only increase F and preserves feasibility, so this convention is conservative for the value recurrence. One may drop the while-loop entirely without affecting Theorem 9 . (ii) The damped update on Line 3 is the defining structural change from DMCG-P: each coordinate j\in B_{i} moves towards 1 by a \delta -fraction of its remaining room (1-\tilde{S}_{i,j}) , rather than by the fixed increment 1/T used by unweighted DMCG-P. This is the multilinear analogue of the Feldman–Naor–Schwartz measured continuous greedy update. H.5.2 Feasibility and coordinate bound Lemma 9 (Feasibility) . For every i\in\{0,1,\dots,k\} , \tilde{S}_{i}\in P and \tilde{S}_{i}\in[0,1]^{\mathcal{N}} . Proof. For each coordinate j , let m_{i,j}\triangleq|\{\tau0 for every e\in\mathcal{N} , the curvature parameter satisfies c_{f}\leq 1 if and only if f is monotone. Proof of Proposition 1 . (\Rightarrow) If f is monotone, then f\left(X\cup Y\right)-f\left(X\right)\geq 0 and f\left(Y\setminus X\right)\geq 0 , so the ratio is non-negative and c_{f}\leq 1 . (\Leftarrow) If c_{f}\leq 1 , suppose for contradiction there exist X,Y with f\left(X\cup Y\right)-f\left(X\right)<0 . Decomposing Y\setminus X=\{e_{1},\ldots,e_{m}\} and writing Y_{i}=\{e_{1},\ldots,e_{i}\} , the telescoping sum f\left(X\cup Y\right)-f\left(X\right)=\sum_{i=1}^{m}\Delta\left(e_{i}|X\cup Y_{i-1}\right) is negative, so some marginal \Delta\left(e_{i}|X\cup Y_{i-1}\right)<0 . Since \Delta\left(e_{i}|\emptyset\right)>0 by assumption, the ratio \Delta\left(e_{i}|X\cup Y_{i-1}\right)/\Delta\left(e_{i}|\emptyset\right)<0 and c_{f}\geq 1-\Delta\left(e_{i}|X\cup Y_{i-1}\right)/\Delta\left(e_{i}|\emptyset\right)>1 , a contradiction. Therefore f\left(X\cup Y\right)\geq f\left(X\right) for all X,Y , so f is monotone. ∎ Restatement of Proposition 2 . For a monotone submodular function, the set-wise curvature c_{f} equals the Conforti–Cornuéjols total curvature \alpha=1-\min_{e:f\left(e\right)>0}\frac{\Delta\left(e|\mathcal{N}\setminus e\right)}{\Delta\left(e|\emptyset\right)}. Proof of Proposition 2 . We prove the two inequalities separately. Upper bound c_{f}\leq\alpha . Fix an admissible pair X,Y with f\left(Y\setminus X\right)>0 , and write Z=Y\setminus X=\{z_{1},\dots,z_{m}\} in an arbitrary order. By telescoping and submodularity, f\left(X\cup Y\right)-f\left(X\right)=\sum_{t=1}^{m}\Delta\left(z_{t}|X\cup\{z_{1},\dots,z_{t-1}\}\right)\geq\sum_{t=1}^{m}\Delta\left(z_{t}|\mathcal{N}\setminus z_{t}\right). The definition of \alpha gives \Delta\left(z_{t}|\mathcal{N}\setminus z_{t}\right)\geq(1-\alpha)\Delta\left(z_{t}|\emptyset\right) for each t . Since f is monotone submodular, it is subadditive, so \sum_{t}\Delta\left(z_{t}|\emptyset\right)=\sum_{t}f\left(z_{t}\right)\geq f\left(Z\right)=f\left(Y\setminus X\right) . Therefore f\left(X\cup Y\right)-f\left(X\right)\geq(1-\alpha)f\left(Y\setminus X\right), and every admissible ratio in Definition 1 is at least 1-\alpha . Lower bound c_{f}\geq\alpha . Let e attain the minimum in the definition of \alpha . Use Definition 1 with X=\mathcal{N}\setminus e and Y=\{e\} . The denominator is f\left(e\right)>0 , and the ratio is exactly \Delta\left(e|\mathcal{N}\setminus e\right)/f\left(e\right)=1-\alpha . Hence the minimum ratio in Definition 1 is at most 1-\alpha , so c_{f}\geq\alpha . ∎ Restatement of Proposition 3 . If f is normalized, symmetric ( f\left(S\right)=f\left(\mathcal{N}\setminus S\right) ), and submodular, and has a positive singleton, then f is non-negative and c_{f}=2 . Proof of Proposition 3 . First, f is non-negative. Applying submodularity to S and \mathcal{N}\setminus S gives f(S)+f(\mathcal{N}\setminus S)\geq f(\mathcal{N})+f(\emptyset)=0 ; by symmetry, the left-hand side is 2f(S) . Upper bound ( c_{f}\leq 2 ): For any X,Y with f\left(Y\setminus X\right)>0 , write Z=Y\setminus X , so Z\cap X=\emptyset and X\cup Y=X\cup Z . Submodularity applied to X\cup Z and \mathcal{N}\setminus Z gives f\left(X\cup Z\right)+f\left(\mathcal{N}\setminus Z\right)\geq f\left(\mathcal{N}\right)+f\left(X\right) . By symmetry and normalization, f\left(\mathcal{N}\setminus Z\right)=f\left(Z\right) and f\left(\mathcal{N}\right)=0 , hence f\left(X\cup Y\right)-f\left(X\right)\geq-f\left(Y\setminus X\right) , giving ratio \geq-1 , hence c_{f}\leq 2 . Lower bound ( c_{f}\geq 2 ): choose a singleton Y=\{e\} with f\left(Y\right)>0 , which exists by hypothesis, and set X=\mathcal{N}\setminus Y . Then (f\left(X\cup Y\right)-f\left(X\right))/f\left(Y\right)=(f\left(\mathcal{N}\right)-f\left(X\right))/f\left(Y\right)=(f\left(\mathcal{N}\right)-f\left(Y\right))/f\left(Y\right) . Since f\left(\mathcal{N}\right)=f\left(\emptyset\right)=0 (by symmetry and normalization), this equals -1 , giving c_{f}\geq 2 . ∎ Restatement of Proposition 7 . Let f be normalized submodular with f\left(e\right)>0 for every singleton. If f takes a negative value, then the multilinear-extension curvature c_{F} is infinite. Proof of Proposition 7 . Let \mathcal{N}^{\prime}\subseteq\mathcal{N} be inclusion-minimal with f\left(\mathcal{N}^{\prime}\right)<0 ; minimality gives f\left(S\right)\geq 0 for all S\subsetneq\mathcal{N}^{\prime} , and |\mathcal{N}^{\prime}|\geq 2 since f\left(e\right)>0 for every singleton. Pick any e^{\prime}\in\mathcal{N}^{\prime} and define \mathbf{y}=\mathbf{1}_{\mathcal{N}^{\prime}} , \mathbf{x}_{\varepsilon}=(1-\varepsilon)\,\mathbf{1}_{\mathcal{N}^{\prime}\setminus\{e^{\prime}\}} for \varepsilon\in(0,1) . Then \mathbf{z}_{\varepsilon}\mathrel{:=}\mathbf{y}-\mathbf{x}_{\varepsilon}\land\mathbf{y}=\varepsilon\,\mathbf{1}_{\mathcal{N}^{\prime}\setminus\{e^{\prime}\}}+\mathbf{1}_{\{e^{\prime}\}} and \mathbf{x}_{\varepsilon}\lor\mathbf{y}=\mathbf{1}_{\mathcal{N}^{\prime}} . The denominator D(\varepsilon)=F(\mathbf{z}_{\varepsilon}) is continuous with D(0)=f\left(e^{\prime}\right)>0 and D(1)=f\left(\mathcal{N}^{\prime}\right)<0 . Let \varepsilon_{0}=\inf\{\varepsilon\in(0,1):D(\varepsilon)\leq 0\} ; by continuity, D(\varepsilon_{0})=0 and D(\varepsilon)>0 for all \varepsilon<\varepsilon_{0} . The numerator satisfies F(\mathbf{x}_{\varepsilon}\lor\mathbf{y})-F(\mathbf{x}_{\varepsilon})=f\left(\mathcal{N}^{\prime}\right)-F\bigl((1{-}\varepsilon)\,\mathbf{1}_{\mathcal{N}^{\prime}\setminus\{e^{\prime}\}}\bigr)\leq f\left(\mathcal{N}^{\prime}\right)<0 for all \varepsilon , since (1{-}\varepsilon)\,\mathbf{1}_{\mathcal{N}^{\prime}\setminus\{e^{\prime}\}} samples only subsets of \mathcal{N}^{\prime}\setminus\{e^{\prime}\} , all having f\geq 0 by minimality. As \varepsilon\to\varepsilon_{0}^{-} , the denominator D(\varepsilon)\to 0^{+} while the numerator stays at most f\left(\mathcal{N}^{\prime}\right)<0 , so the ratio diverges to -\infty and c_{F}=\infty . ∎ Restatement of Theorem 3 . Let f be normalized submodular with positive singleton values. If f is strictly positive on every nonempty set, then c_{F}=c_{f} ; if f takes a negative value, then c_{F}=\infty . Proof of Theorem 3 . Part (b) is Proposition 7 . For part (a), we show c_{F}\leq c_{f} (equality then follows from Proposition 6 ). For \mathbf{x},\mathbf{y}\in[0,1]^{\mathcal{N}} , construct a coupling (R_{1},R_{2})\sim\mathcal{D}(\mathbf{x},\mathbf{y}) where each element i satisfies: \Pr[i\in R_{1}]=x_{i} , \Pr[i\in R_{2}\mid i\in R_{1}]=0 , \Pr[i\in R_{2}\mid i\notin R_{1}]=(y_{i}-\min(x_{i},y_{i}))/(1-x_{i}) . When x_{i}=1 , the event i\notin R_{1} has probability zero; define the last conditional probability arbitrarily, say as 0 . Then R_{1}\sim\mathcal{R}(\mathbf{x}) , R_{2}\sim\mathcal{R}(\mathbf{y}-\mathbf{x}\land\mathbf{y}) , R_{1}\cup R_{2}\sim\mathcal{R}(\mathbf{x}\lor\mathbf{y}) , and R_{1}\cap R_{2}=\emptyset . When R_{2}\neq\emptyset , strict positivity gives f\left(R_{2}\right)>0 , so the curvature inequality f\left(R_{1}\cup R_{2}\right)-f\left(R_{1}\right)\geq(1-c_{f})\,f\left(R_{2}\right) applies by Definition 1 . When R_{2}=\emptyset , both sides equal zero. Thus the inequality holds for all realizations of (R_{1},R_{2}) . Taking expectations: F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{x})\geq(1-c_{f})\,F(\mathbf{y}-\mathbf{x}\land\mathbf{y}) , giving c_{F}\leq c_{f} . ∎ Proposition 11 (OPT-aware decomposable curvature bound) . For f=g-\ell with g monotone submodular of CC curvature \alpha_{g} and \ell non-negative modular, let A_{0},A_{1},\dots be the active-set trajectory of greedy with pruning and \mathcal{O} the set of optimal cardinality-feasible solutions. If r=\max_{O^{*}\in\mathcal{O}}\max_{i:f\left(A_{i}\setminus O^{*}\right)>0}\frac{\ell(A_{i}\setminus O^{*})}{g(A_{i}\setminus O^{*})}, then c_{g}\leq\alpha_{g}/(1-r) . Proof of Proposition 11 . Fix any O^{*}\in\mathcal{O} and any trajectory step i with f\left(A_{i}\setminus O^{*}\right)>0 . Apply the decomposition f=g-\ell with X=O^{*} , Y=A_{i} : \displaystyle f\left(O^{*}\cup A_{i}\right)-f\left(O^{*}\right) \displaystyle=[g(O^{*}\cup A_{i})-g(O^{*})]-\ell(A_{i}\setminus O^{*}) \displaystyle\geq(1-\alpha_{g})\,g(A_{i}\setminus O^{*})-\ell(A_{i}\setminus O^{*}), where the inequality uses the CC curvature bound on g . The denominator g(A_{i}\setminus O^{*}) is positive on every qualifying step, because g(A_{i}\setminus O^{*})=f\left(A_{i}\setminus O^{*}\right)+\ell(A_{i}\setminus O^{*}) and both terms on the right are non-negative with f\left(A_{i}\setminus O^{*}\right)>0 . Writing r_{i}=\ell(A_{i}\setminus O^{*})/g(A_{i}\setminus O^{*}) and f\left(A_{i}\setminus O^{*}\right)=(1-r_{i})\,g(A_{i}\setminus O^{*}) : \frac{f\left(O^{*}\cup A_{i}\right)-f\left(O^{*}\right)}{f\left(A_{i}\setminus O^{*}\right)}\;\geq\;\frac{(1-\alpha_{g})-r_{i}}{1-r_{i}}\;=\;1-\frac{\alpha_{g}}{1-r_{i}}\;\geq\;1-\frac{\alpha_{g}}{1-r}, where the last inequality uses r_{i}\leq r by definition of r (which maximizes over all O^{*}\in\mathcal{O} and all trajectory steps). Since this holds for every O^{*} and every qualifying step i , taking the double minimum in Definition 2 : c_{g}\;=\;1-\min_{O^{*}\in\mathcal{O}}\;\min_{i:\,f\left(A_{i}\setminus O^{*}\right)>0}\frac{f\left(O^{*}\cup A_{i}\right)-f\left(O^{*}\right)}{f\left(A_{i}\setminus O^{*}\right)}\;\leq\;\frac{\alpha_{g}}{1-r}.\qed Restatement of Proposition 5 . For the GCLin objective f\left(S\right)=R(S)-\lambda D(S),\qquad R(S)=\sum_{i\in\mathcal{N}}\sum_{j\in S}s_{i,j},\qquad D(S)=\sum_{\begin{subarray}{c}i,j\in S\\ i\neq j\end{subarray}}s_{i,j}, with symmetric non-negative similarities s_{i,j} , uniform query weights ( w_{i}=1 ), and 0\leq\lambda\leq 1 , the curvature satisfies c_{f}\leq 2\lambda . Proof of Proposition 5 . Let B=T\setminus S , and consider only pairs with f\left(B\right)>0 , as in Definition 1 . By symmetry of the similarities, for any S,T\subseteq\mathcal{N} : \displaystyle f\left(S\cup T\right)-f\left(S\right) \displaystyle=f\left(B\right)-2\lambda\sum_{i\in S}\sum_{j\in B}s_{i,j} \displaystyle\geq f\left(B\right)-2\lambda\sum_{i\in\mathcal{N}\setminus B}\sum_{j\in B}s_{i,j}. The remaining cross-similarity term is controlled by the standalone GCLin value of B when \lambda\leq 1 : \sum_{i\in\mathcal{N}\setminus B}\sum_{j\in B}s_{i,j}=\sum_{i\in\mathcal{N}}\sum_{j\in B}s_{i,j}-\sum_{i\in B}\sum_{j\in B}s_{i,j}\leq\sum_{i\in\mathcal{N}}\sum_{j\in B}s_{i,j}-\lambda\sum_{i\in B}\sum_{j\in B}s_{i,j}\leq f\left(B\right). Hence f\left(S\cup T\right)-f\left(S\right)\geq(1-2\lambda)f\left(B\right)=(1-2\lambda)f\left(T\setminus S\right). Therefore c_{f}\leq 2\lambda . The monotonicity claim used in Section 4.3 for \lambda\leq 1/2 follows from the corresponding singleton marginal: for e\notin S , f\left(S\cup\{e\}\right)-f\left(S\right)=s_{e,e}+(1-2\lambda)\sum_{i\in S}s_{i,e}+\sum_{i\in\mathcal{N}\setminus(S\cup\{e\})}s_{i,e}\geq 0. ∎ Remark 13 . The restriction \lambda\leq 1 is not a proof artifact. For \lambda>1 , the positive standalone value f\left(B\right)=R(B)-\lambda D(B) can be arbitrarily small relative to the cross-similarity \sum_{i\in S,j\in B}s_{i,j} , so the argument above gives no uniform 2\lambda curvature bound without an additional cross-redundancy condition. The \lambda=1.5 experiments in Section 4.3 are therefore reported only as empirical trajectory diagnostics. Restatement of Proposition 10 . For the DR-submodular quadratic objective F(\mathbf{x})=\frac{1}{2}\mathbf{x}^{\top}\mathbf{H}\mathbf{x}-\beta\,\mathbf{u}^{\top}\mathbf{H}\mathbf{x}, where \mathbf{H} is symmetric entry-wise non-positive, \mathbf{x}\leq\mathbf{u} on the polytope, and \beta\in(1/2,1) , the instance is normalized, non-negative, DR-submodular, and has c_{F}\leq 2/(2\beta-1) . It is non-monotone whenever (\mathbf{H}\mathbf{u})_{j}<0 for some feasible coordinate j . Proof of Proposition 10 . Normalization and DR-submodularity. We have F(\mathbf{0})=0 . The Hessian of F is exactly \mathbf{H} , whose off-diagonal entries are non-positive by assumption, so every first partial derivative is coordinate-wise non-increasing in the other coordinates. This is precisely DR-submodularity for smooth functions. Non-monotonicity in nondegenerate instances. The gradient is \nabla F(\mathbf{x})=\mathbf{H}\mathbf{x}-\beta\mathbf{H}\mathbf{u} . At \mathbf{x}=\mathbf{u} , \nabla F(\mathbf{u})=(1-\beta)\mathbf{H}\mathbf{u} . Thus, if (\mathbf{H}\mathbf{u})_{j}<0 for some feasible coordinate j , the marginal in that coordinate is negative at \mathbf{u} , and the objective is not monotone on the feasible box. Non-negativity. For \mathbf{x}\in\mathcal{P} , since \mathbf{x}\leq\mathbf{u} and \mathbf{H} is entry-wise non-positive, we have \mathbf{x}^{\top}\mathbf{H}\mathbf{x}\geq\mathbf{u}^{\top}\mathbf{H}\mathbf{x} and \mathbf{u}^{\top}\mathbf{H}\mathbf{x}\leq 0 . Therefore F(\mathbf{x})=\tfrac{1}{2}\mathbf{x}^{\top}\mathbf{H}\mathbf{x}-\beta\,\mathbf{u}^{\top}\mathbf{H}\mathbf{x}\geq(\tfrac{1}{2}-\beta)\,\mathbf{u}^{\top}\mathbf{H}\mathbf{x}\geq 0 . Curvature. For \mathbf{x},\mathbf{y}\in\mathcal{P} , let \mathbf{z}=\mathbf{y}-\mathbf{x}\land\mathbf{y} . Then F(\mathbf{z})=\tfrac{1}{2}\mathbf{z}^{\top}\mathbf{H}\mathbf{z}-\beta\,\mathbf{u}^{\top}\mathbf{H}\mathbf{z}\geq(\tfrac{1}{2}-\beta)\,\mathbf{u}^{\top}\mathbf{H}\mathbf{z}\geq(\tfrac{1}{2}-\beta)\,\mathbf{x}^{\top}\mathbf{H}\mathbf{z} , where the last step uses \mathbf{x}\leq\mathbf{u} and \mathbf{H}\mathbf{z}\leq\mathbf{0} . Also F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{x})=F(\mathbf{z})+\mathbf{z}^{\top}\mathbf{H}\mathbf{x}\geq F(\mathbf{z})+\tfrac{1}{\tfrac{1}{2}-\beta}\,F(\mathbf{z})=(1+\tfrac{1}{\tfrac{1}{2}-\beta})\,F(\mathbf{z}) . Since \tfrac{1}{2}-\beta<0 , this gives F(\mathbf{x}\lor\mathbf{y})-F(\mathbf{x})\geq(1-\tfrac{2}{2\beta-1})\,F(\mathbf{z}) , hence c_{F}\leq\tfrac{2}{2\beta-1} . ∎