Pith. sign in

REVIEW 3 major objections 6 minor 19 references

Submodular Maximization under Supermodular Constraint: Greedy Guarantees

T0 review · 3 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that a ratio-marginal greedy algorithm achieves a (1−e^{−(1−γ)}) approximation for submodular maximization under a supermodular cost constraint with curvature γ, and that this bound is tight.

desk verdict The main curvature-based greedy guarantee is real and new, and the reported "S=∅ makes γ=0" bug does not hold up on inspection; the real problems are an incomplete tightness proof and a missing lemma. read the letter →

arxiv 2602.16240 v2 pith:LMHEYYDL submitted 2026-02-18 cs.DS cs.CC

Ajitesh Srivastava , Shanghua Teng This is my paper
classification cs.DScs.CC MSC 90C2768W25
keywords submodularmaximizationsupermodularconstraintsgreedyalgorithmcurvaturebicriteriaapproximationknapsackconstraintdualproblemagentselection
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tackles a long-standing gap in greedy approximation: maximizing a monotone submodular objective (like coverage or information gain) subject to a supermodular cost constraint, where the marginal cost of adding elements grows as the set expands. The authors show that a simple ratio-marginal greedy algorithm—always pick the element maximizing marginal gain per marginal cost—achieves a (1−e^{−(1−γ)}) approximation of the optimum, while exceeding the cost budget by at most a (2−γ)/(1−γ) factor, where γ is the curvature of the supermodular cost. They prove this approximation factor is tight for the greedy rule, and give sharper bounds when the objective has bounded submodular curvature. A binary-search wrapper converts the primal guarantee into a bicriteria approximation for the dual problem of minimizing supermodular cost subject to a submodular coverage target. If the curvature assumption holds, these constitute the first constant-factor guarantees for this problem family, and experiments on simulated multi-agent debate support the practical competitiveness of the greedy rule.

What carries the argument

The central object is the supermodular curvature γ, defined by the minimum of g(T)/g(T|S) over sets with g(T) ≥ g(S), which measures how far g is from being linear (γ=0 for modular functions). The load-bearing inequality derived from this definition is g(S*|S_i) ≤ g(S*)/(1−γ), which the proof needs at every greedy step. Combined with the ratio-marginal selection rule, this yields a discrete recurrence f_{i+1}−f_i ≥ (f*−f_i)(1−γ)(G_{i+1}−G_i), whose solution gives the (1−e^{−(1−γ)}) bound. The tightness construction uses a max-cover instance with a supermodular 'jump' in cost to force the greedy algorithm onto a path that matches the bound as the instance size grows.

What would settle it

Take g(S)=|S|^2 and evaluate Eq. (2) as printed, including S=∅: the ratio g(T)/g(T|∅)=1 for every T, so γ=0. Plugging this into Theorem 3.1 claims a (1−e^{−1}) constant-factor approximation for a supermodular-knapsack instance, directly contradicting the Proposition 1.1 hardness bound. A reader can run this two-line check to settle whether the theorem's hypothesis is satisfiable in its stated form.

Watch

Extended reading notes

Core claim

For any monotone submodular f and monotone supermodular g with curvature γ<1, the ratio-greedy algorithm that stops at the first budget violation returns a set S_k with g(S_k) ≤ (2−γ)/(1−γ)·θ and f(S_k) ≥ (1−e^{−(1−γ)}) f(S*). The factor (1−e^{−(1−γ)}) is tight for this algorithm. When f has submodular curvature c, the guarantee improves to 1−(1−(1−c)(1−γ))^{1/(1−c)}, and continuing to run the algorithm past the budget yields a closed-form trade-off between the overflow factor β+ and the achieved approximation. For the dual problem—minimizing g subject to f(S) ≥ τ—the paper shows that binary search on the budget, using any (α,β) primal algorithm, yields a (β(1+ε/B*), α) bicriteria approximat

Load-bearing premise

The curvature definition in Eq. (2), if read literally with S=∅ included in the minimum, yields γ=0 for every function, which would make the main theorem vacuous and contradict the paper's own hardness result; the proof requires the minimum to be restricted to nonempty, essentially disjoint sets T with g(T) ≥ g(S), a restriction the paper never states.

Editorial extensions

If this is right

  • For any monotone submodular objective and supermodular cost with curvature γ<1, ratio-greedy at first overflow gives a (1−e^{−(1−γ)}, (2−γ)/(1−γ)) bicriteria approximation.
  • The (1−e^{−(1−γ)}) factor is tight for the greedy algorithm, so no better guarantee is obtainable from the ratio-marginal rule without additional assumptions.
  • When the objective has submodular curvature c, the approximation improves to 1−(1−(1−c)(1−γ))^{1/(1−c)}; in the modular case c=γ=0 it recovers the classical knapsack exact-ratio limit with a 2× budget violation.
  • Running greedy beyond the budget improves the approximation as a function of the overflow factor β+, specified by the paper's closed-form bound.
  • Binary search on the budget converts any (α,β) primal algorithm into a (β(1+ε/B*), α) bicriteria approximation for the dual supermodular minimization problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the curvature definition in Eq. (2) is repaired to exclude empty sets and to require essentially disjoint T with g(T)≥g(S), the main theorem survives; but Proposition 1.1's hardness implies the guarantee cannot extend to general supermodular costs with γ=0, so the curvature restriction is not decorative.
  • The dual binary-search reduction is generic: it would work with any primal (α,β) algorithm, not just the greedy one, so future improvements to primal algorithms would immediately transfer to the supermodular cover problem.
  • The tightness construction suggests the greedy rule's worst case is a single supermodular 'jump' in cost rather than smooth curvature; instances with smoothly growing quadratic costs should behave far better in practice than the worst-case bound.
  • In the LLM debate simulator, the cost function's curvature is bounded by γ≤2/3, which predicts that ratio-greedy should reach at least 1−e^{−1/3}≈0.28 of the optimal objective before overflow—a testable quantitative claim within the same simulator.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper considers maximizing a monotone submodular function f subject to an upper-bound constraint g(S)≤θ, where g is a monotone supermodular cost function. It introduces a new curvature parameter γ for g, proposes a greedy algorithm that iteratively selects the element maximizing the ratio of marginal objective gain to marginal cost, and claims bicriteria approximation guarantees: before stopping at first budget violation, f(S_k)≥(1−e^{−(1−γ)})f(S*) and g(S_k)≤((2−γ)/(1−γ))θ. It extends the bound when f has submodular curvature c, analyzes continued overflow, and gives a binary-search reduction for the dual problem of minimizing g under f(S)≥τ. The paper also reports experiments on a simulated multi-agent debate setup.

Significance. If the main theorems were correct, this would be a valuable contribution: it would give the first constant-factor bicriteria guarantees for a class of supermodular-cost constraints that had no prior approximations, with explicit dependence on a curvature parameter that is less restrictive than previous definitions. The paper also includes a tightness construction and a dual reduction, and it provides reproducible code. However, as submitted, the central curvature definition in Eq. (2) is degenerate (γ≡0), so the stated guarantees are not meaningful; and the tightness construction is incomplete. These issues are load-bearing and prevent acceptance in the current form.

major comments (3)
  1. [Eq. (2), Theorem 3.1] Eq. (2): as written the minimization is over all pairs with g(T)≥g(S), including S=∅. Since g(∅)=0, g(T)/g(T|∅)=g(T)/g(T)=1 for every T, so γ=0 for every function g. Then Theorem 3.1 would give a (1−1/e)-approximation with 2θ cost violation for all supermodular constraints, contradicting Proposition 1.1. The proof of Theorem 3.1 uses (14) g(S*|S_i) ≤ g(S*)/(1−γ), valid only if the admissible pairs exclude S=∅ and T=S and satisfy an appropriate normalization. The paper never states this restriction. All quantitative claims in Theorems 1.2, 3.1, 3.5 depend on this parameter; the definition must be repaired and each use re-verified.
  2. [Appendix A.1 (Theorem 3.4)] Appendix A.1 (Theorem 3.4): the tightness instance only specifies g on singletons and on V_k'∪{o_j}. Supermodularity of the full set function is not proved, and curvature is computed from one pair g(V_k')/g(V_k'|o_j). To claim curvature γ, one must define g for all subsets, prove supermodularity, and show the minimum in (2) over the admissible family is attained at that pair. Without this, Theorem 3.4 is unsupported.
  3. [Theorem 3.1, Eq. (5)] The cost bound (5) of Theorem 3.1 is not justified. The proof says 'we can remove any element from the given set that by itself would have violated the constraint,' but this changes the returned set and may invalidate the f guarantee. Without an explicit preprocessing step excluding elements with g({e})>θ, the bound can fail: take θ=1, g({a})=10, g({b})=0.1, g({a,b})=20, and f modular with f({a})=100, f({b})=1; the greedy algorithm selects a first, giving g(S_1)=10 > ((2−γ)/(1−γ))θ for small γ. State the preprocessing assumption in the algorithm and theorem.
minor comments (6)
  1. [Section 2] Typo: 'gorunded' should be 'grounded'.
  2. [Eq. (2)] The notation g(T|S) is used without definition; define g(T|S)=g(S∪T)−g(S). Also specify S,T⊆V and require the marginal to be positive.
  3. [Proposition 1.1] The reduction says the solution satisfies g(S)≥θ, but the constraint in (1) is g(S)≤θ. Correct the direction.
  4. [Theorem 3.6] The displayed formula is garbled (unbalanced parentheses and exponent formatting); restate it in the same notation as the proof.
  5. [Appendix A.3] 'Applying Lemma??' should cite Lemma A.3.
  6. [Algorithm 1 / Theorem 3.7] State the assumption that a feasible solution with f≥τ exists (otherwise no R succeeds), and make explicit the invariant that the binary search brackets a success/failure transition.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the main derivation is self-contained. A degenerate curvature definition is a correctness gap, not a circular fit.

full rationale

The paper's central claim (Theorem 3.1) is derived in-line from the greedy ratio rule, submodularity/supermodularity inequalities, and the curvature parameter defined in Eq. (2); no fitted parameter is later presented as a prediction, and no load-bearing self-citation appears (the cited prior work [1,7] is external). The tightness construction in Theorem 3.4 explicitly chooses k'=(k+epsilon)(1-gamma) so that the constructed instance has the desired curvature and the ratio tends to 1-e^{-(1-gamma)}; this is a standard worst-case construction rather than a prediction forced by the construction. The one serious concern is formal, not circular: Eq. (2) as printed minimizes over S=empty, which gives g(T)/g(T|empty)=1 and hence gamma=0 for every normalized g, and the proof's Inequality (14) requires the unstated condition g(S_i)<=g(S*) (the paper itself notes 'the above bound applies only for g(S_{k-1})<=g(S*) due to the use of our curvature definition'). That makes the theorem's quantitative claims depend on a definition that does not say what the proof needs, but this is a definitional flaw/gap in the derivation rather than a case where the result is equivalent to its inputs by construction. Experiments are empirical and do not feed back into the theory. Therefore no circular step is exhibited, and the circularity score is minimal.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The theoretical claims rest on the paper's new curvature definition and the implicit nonempty/disjoint restriction needed to make Eq. (2) nontrivial; the main proof also assumes infeasible singletons are removed and relies on P≠NP for hardness. No free parameters are fit to data; the only hand-chosen value is k' in the tightness construction.

free parameters (1)
  • k' in tightness construction = (k+ε)(1−γ)
    In the proof of Theorem 3.4, k' is chosen as a function of k and γ to force the greedy ratio. This is a construction parameter for the lower-bound instance, not a parameter of the algorithm or the main theorem.
assumptions (4)
  • ad hoc to paper Curvature definition in Eq (2) is well-defined for all relevant pairs and satisfies g(T|S) ≤ g(T)/(1−γ) when g(T)≥g(S).
    This is the paper's new definition; the inequality is the main tool in Theorem 3.1. The definition as printed is ambiguous because it does not exclude S=∅ or overlapping sets; the intended nonempty restriction is not stated.
  • domain assumption All singleton elements have g({v}) ≤ θ.
    Used in Theorem 3.1 proof to conclude the overflowing element's individual cost ≤ θ; elements that individually exceed the budget are removed without saying so.
  • domain assumption P ≠ NP (or hardness of Maximum Independent Set) for Proposition 1.1.
    The inapproximability claim relies on a reduction from Maximum Independent Set.
  • standard math Standard Bernoulli and telescoping inequalities.
    Used in the recurrence transformations (Lemma A.2, A.3).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Submodular Maximization under Supermodular Constraint: Greedy Guarantees." pith.science (2026). https://pith.science/paper/LMHEYYDL

@misc{pith2026260216240,
  author       = {Pith},
  title        = {Pith review of: Submodular Maximization under Supermodular Constraint: Greedy Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LMHEYYDL}},
  note         = {Machine review of arXiv:2602.16240}
}
abstract

Motivated by a wide range of applications in data mining and machine learning, we consider the problem of maximizing a submodular function subject to supermodular cost constraints. In contrast to the well-understood setting of cardinality and matroid constraints, where greedy algorithms admit strong guarantees, the supermodular constraint regime remains poorly understood -- guarantees for greedy methods and other efficient algorithmic paradigms are largely open. We study this family of fundamental optimization problems under an upper-bound constraint on a supermodular cost function with curvature parameter $\gamma$. Our notion of supermodular curvature is less restrictive than prior definitions, substantially expanding the class of admissible cost functions. We show that our greedy algorithm, which iteratively includes elements maximizing the ratio of the objective and constraint functions, achieves a $\left(1 - e^{-(1-\gamma)}\right)$-approximation before stopping. We prove that this approximation is indeed tight for this algorithm. Further, if the objective function has a submodular curvature $c$, then we show that the bound further improves to $\left(1 - (1- (1-c)(1-\gamma))^{1/(1-c)}\right)$, which can be further improved by continuing to violate the constraint. Finally, we show that the Greedy-Ratio-Marginal in conjunction with binary search leads to a bicriteria approximation for the dual problem -- minimizing a supermodular function under a lower bound constraint on a submodular function. We conduct a number of experiments on a simulation of LLM agents debating over multiple rounds -- the task is to select a subset of agents to maximize correctly answered questions. Our algorithm outperforms all other greedy heuristics, and on smaller problems, it achieves the same performance as the optimal set found by exhaustive search.

Figures

Figures reproduced from arXiv: 2602.16240 by the authors.

Figure 1
Figure 1. Summary of our results for submodular maximization with supermodular constraint: We find the approximation [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Instance of max cover with supermodular cost. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Comparison with 100 agents and 1000 questions with the “Global View” model. [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Comparison with 100 agents and 1000 questions with the “Local View” model. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Comparison including the optimal solution for 15 [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Instance of max cover with supermodular cost. [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Comparison with 100 agents and 1000 questions with the “Global View” model. [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: Comparison with 100 agents and 1000 questions with the “Global View” model. [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: Comparison including the optimal solution for 15 agents and 100 questions. [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 2 canonical work pages

  1. [1]

    Wenruo Bai and Jeff Bilmes. 2018. Greed is still good: maximizing monotone sub- modular+ supermodular (BP) functions. InInternational Conference on Machine Learning. PMLR, 304–313

    2018

  2. [2]

    Girish Chandrashekar and Ferat Sahin. 2014. A survey on feature selection methods.Computers & electrical engineering40, 1 (2014), 16–28

    2014

  3. [3]

    Chandra Chekuri, Kent Quanrud, and Manuel R Torres. 2022. Densest subgraph: Supermodularity, iterative peeling, and flow. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1531–1555

    2022

  4. [4]

    Ruoyu Chen, Hua Zhang, Siyuan Liang, Jingzhi Li, and Xiaochun Cao. 2024. Less is more: Fewer interpretable region via submodular subset selection.arXiv preprint arXiv:2402.09164(2024)

    arXiv 2024

  5. [5]

    Wenjing Chen and Victoria Crawford. 2023. Bicriteria approximation algorithms for the submodular cover problem.Advances in Neural Information Processing Systems36 (2023), 72705–72716

    2023

  6. [6]

    Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch

  7. [7]

    Moran Feldman and Alan Kuhnle. 2025. Bicriteria submodular maximization. arXiv preprint arXiv:2507.10248(2025)

    arXiv 2025

  8. [8]

    Johan Håstad. 1999. Clique is hard to approximate within n 1-𝜀. (1999)

    1999

Show all 19 references
  1. [9]

    Md Rafiul Islam, Tamer Oraby, Audrey McCombs, Mohammad Mihrab Chowd- hury, Mohammad Al-Mamun, Michael G Tyshenko, and Claus Kadelka. 2021. Evaluation of the United States COVID-19 vaccine allocation strategy.PloS one 16, 11 (2021), e0259700

    2021

  2. [10]

    David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. InProceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 137–146

    2003

  3. [11]

    Suraj Kothawade, Vishal Kaushal, Ganesh Ramakrishnan, Jeff Bilmes, and Rishabh Iyer. 2022. Prism: A rich class of parameterized submodular information measures for guided data subset selection. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 10238–10246

    2022

  4. [12]

    George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functions—I.Mathematical programming14, 1 (1978), 265–294

    1978

  5. [13]

    Madhavan R Padmanabhan, Yanhui Zhu, Samik Basu, and Aduri Pavan. 2023. Maximizing submodular functions under submodular constraints. InUncertainty in Artificial Intelligence. PMLR, 1618–1627

    2023

  6. [14]

    Majun Shi, Zishen Yang, and Wei Wang. 2025. Submodular + Supermodular function maximization with knapsack constraint.Discrete Applied Mathematics 377 (2025), 113–133. doi:10.1016/j.dam.2025.06.062

    2025 doi

  7. [15]

    Maxim Sviridenko, Jan Vondrák, and Justin Ward. [n. d.].Optimal approximation for submodular and supermodular optimization with bounded curvature. 1134–

  8. [16]

    Fan Yang, Kai He, Linxiao Yang, Hongxia Du, Jingbang Yang, Bo Yang, and Liang Sun. 2021. Learning interpretable decision rule sets: A submodular optimization approach.Advances in Neural Information Processing Systems34 (2021), 27890– 27902

    2021

  9. [17]

    Global View

    Xueliang Zhao, Wei Wu, Jian Guan, Qintong Li, and Lingpeng Kong. 2025. Dy- naAct: Large Language Model Reasoning with Dynamic Action Spaces.arXiv preprint arXiv:2511.08043(2025). 9 A Complete Proofs A.1 Tightness of Greedy for Supermodular Constraints Theorem 3.4 (Tightness of...

    2025

  10. [1148]

    1137/1.9781611973730.76

    arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611973730.76 doi:10. 1137/1.9781611973730.76

    doi

  11. [2023]

    InForty-first International Conference on Machine Learning

    Improving factuality and reasoning in language models through multiagent debate. InForty-first International Conference on Machine Learning

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.