Pith. sign in

REVIEW 2 major objections 7 minor 1 cited by

Bicriteria Submodular Maximization

T0 review · 2 major / 7 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper establishes the exact bicriteria frontier for monotone submodular maximization under cardinality constraints: a polynomial-time $(1-\varepsilon-o(1),\rho(c,\varepsilon))$ algorithm, matched by a sub-exponential-time lower bound…

desk verdict Strong and novel results, but the tight trade-off for c ≥ 1/2 rests on an unproven discretization of the variable-rate Continuous Double Greedy. read the letter →

arxiv 2507.10248 v1 pith:DTNDIZWT submitted 2025-07-14 cs.DS cs.DM

Moran Feldman , Alan Kuhnle This is my paper
classification cs.DScs.DM MSC 68W2590C27
keywords submodularfunctionbicriteriaapproximationcardinalityconstraintknapsackmatroidmonotonesymmetriccontinuousgreedy
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

The paper studies what happens when an algorithm for maximizing a submodular function may overshoot the constraint by a bounded factor $\beta$: how much of the optimal value $\alpha$ can still be guaranteed? For monotone functions under a cardinality constraint of density $c$ (budget as a fraction of total weight), it proves the answer is exactly $\alpha=1-\varepsilon$ with $\beta=\rho(c,\varepsilon)$, a closed-form function of $c$ and $\varepsilon$, and it supplies both a matching algorithm and a matching inapproximability result. The formula splits at $c=1/2$: a continuous greedy process handles small densities, while a variable-rate variant of continuous double greedy handles large densities. The same machinery yields improved bicriteria guarantees for general and symmetric submodular functions under down-closed convex, matroid, knapsack and cardinality constraints, and shows that allowing constraint violation can beat single-criterion state of the art even when only feasible solutions are ultimately wanted.

What carries the argument

Two continuous dynamics carry the upper bounds. The first is continuous greedy: it increases a fractional solution along a feasible direction at a rate that compensates for the diminishing-returns decay, and its stopping time $T$ controls both the approximation $1-e^{-T}$ and the budget growth. The second is a continuous double-greedy variant that moves two vectors toward each other while scaling by element costs and capping the budget-coordinate growth at $B\rho(c,\varepsilon)$. The matching lower bound is carried by a new family of hard instances built from a function $F(x,y)$ on the density rectangle $[0,c]\times[0,1-c]$; $F$ is engineered so that its partial derivatives are non-negative and non-increasing, which makes the induced set functions monotone and submodular, while their average over a random hidden optimal set is the function $G(x,y)=1-(1-x-y)^{1/c}$. Because sub-exponential query algorithms cannot distinguish the individual instances from the averaged one, their achievable approximation is forced down to exactly $1-\varepsilon$ at infeasibility ratio $\rho(c,\varepsilon)$.

What would settle it

For chosen constants $c\in(0,1)$ and $\varepsilon\in(0,1)$, construct the hard-instance distribution over monotone submodular functions described in Section 4.2.2 and run any candidate algorithm whose infeasibility ratio is exactly $\rho(c,\varepsilon)$ using sub-exponentially many value-oracle queries; if on large instances its expected output value exceeds $1-\varepsilon+\delta$ times the optimum, Theorem 4.7's lower bound is false.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is a complete bicriteria characterization for monotone submodular maximization under a knapsack constraint of density $c$. For $c\le 1/2$ the infeasibility ratio is $\rho(c,\varepsilon)=(1-\varepsilon^c)/c$, and for $c\ge 1/2$ it is $\rho(c,\varepsilon)=(1-2(1-c)\sqrt{\varepsilon}-\varepsilon(2c-1))/c$. The paper proves that the standard continuous greedy algorithm with a carefully chosen stopping time achieves $(1-\varepsilon-o(1),\rho(c,\varepsilon))$ in the first regime, and that a cost-scaled, rate-capped variant of the continuous double-greedy algorithm achieves the same pair in the second. It then proves that no sub-exponential-time algorithm with infeasibility ratio $\rho(c,\varepsilon)$ can guarantee approximation better than $1-\varepsilon+\delta$, so the trade-off is tight up to the $o(1)$ and $\delta$ terms. The same design pattern extends to general submodular functions with a $(1/2-\varepsilon,O(\varepsilon^{-1}))$ guarantee under down-closed convex sets, and to symmetric functions with a density-dependent guarantee of $(1/2-\varepsilon,(1-(2\varepsilon)^c)/(2c))$.

Load-bearing premise

The load-bearing premise is that discretizing the idealized continuous-time greedy algorithms preserves the same infeasibility ratio $\beta$ and loses only a $1-o(1)$ factor in the objective; the paper invokes standard techniques for this step rather than proving it for the new greedy variants.

Editorial extensions

If this is right

  • For a cardinality constraint of density $c$, the function $\rho(c,\varepsilon)$ is the complete frontier: no algorithm with infeasibility ratio $\rho(c,\varepsilon)$ can beat $1-\varepsilon+\delta$, and the paper's algorithm attains $1-\varepsilon-o(1)$.
  • Knapsack constraints inherit the same frontier up to an additive $1$ in infeasibility from rounding, and matroid constraints inherit a $(1-\varepsilon,\lceil\log_2 \varepsilon^{-1}\rceil)$ guarantee from the convex-set result.
  • For general non-monotone submodular functions, a $1/2-\varepsilon$ approximation with $O(\varepsilon^{-1})$ infeasibility is achievable for every down-closed solvable convex set, improving the previous quadratic dependence on $\varepsilon^{-1}$.
  • For symmetric submodular functions, the reduced-rate continuous greedy yields infeasibility ratio $(1-(2\varepsilon)^c)/(2c)$, and for small densities this beats the single-criterion state of the art even when one rounds back to feasible solutions.
  • The inapproximability result for non-down-closed convex sets shows that down-closedness is necessary for any constant bicriteria guarantee, so the algorithmic results are tight in the class of constraints they target.

Reading between the lines

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

  • The rate-capping idea suggests a general recipe: slowing a continuous greedy process converts objective value into feasibility in a controlled way, which may transfer to streaming or distributed submodular maximization where infeasibility is a natural budget metric rather than an error.
  • The new hard instances have a single optimal solution, unlike the symmetric-pair instances used by prior techniques; this may make the construction reusable for regularized objectives or other settings where symmetry gaps cannot be invoked.
  • Until the discretization invoked through standard techniques is written out for the guided, reduced-rate, and variable-rate variants, the cleanest validation is an implementation-level check that the discrete versions preserve the claimed infeasibility ratio on small exhaustive instances.
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

2 major / 7 minor

Summary. The paper initiates a systematic study of bicriteria approximation algorithms for submodular maximization under cardinality, knapsack, matroid, and convex set constraints, covering monotone, general, and symmetric objective functions. The central results are a tight density-dependent trade-off for monotone functions under a cardinality constraint (Theorems 4.6 and 4.7), a (1/2−ε, O(ε^{-1}))-bicriteria algorithm for general submodular functions over down-closed convex sets (Theorem 5.6) with a hardness result for non-down-closed sets, and improved bounds for symmetric functions, including a reduced-rate continuous greedy algorithm (Theorem 6.6). The paper also gives simple combinatorial greedy algorithms for knapsack and matroid constraints. The proofs are extensive and mostly self-contained, and the hard-instance construction for c ≤ 1/2 is a novel feature that goes beyond the symmetry-gap technique.

Significance. If the proofs are correct, the paper closes the gap left by Filmus et al. for density-dependent cardinality constraints and completely determines the bicriteria trade-off for monotone objectives, which is a result of clear significance. The new hard-instance family for c ≤ 1/2 is an important technical advance, since the symmetry-gap technique provably fails there. The results also improve the state of the art for general submodular maximization, replacing Crawford's O(ε^{-2}) infeasibility with O(ε^{-1}), and for symmetric functions, where Corollary 6.7 beats prior single-criterion algorithms for small densities. The paper is unusually thorough in deriving its main results from stated lemmas, and the main theorems explicitly display the o(1) error terms, which is commendable.

major comments (2)
  1. [§4.2.1 (Algorithm 2; paragraph before Lemma 4.9)] The proof of Theorem 4.6 for c ≥ 1/2 relies on the continuous-time analysis of Algorithm 2. The paragraph before Lemma 4.9 states that the “standard techniques of [9]” yield an implementable version with only a 1 − o(1) loss in the objective, but it does not describe the discrete algorithm or prove that the infeasibility ratio ρ(c, ε) is preserved. This point is load-bearing: Corollary 4.11 bounds the cost of the continuous trajectory pointwise, and Theorem 4.7 gives hardness for exactly β = ρ(c, ε) with no additive slack. The manuscript should specify the discretized update rule and demonstrate both that each discrete direction satisfies ⟨p, d⟩ ≤ Bρ(c, ε) (which a natural Euler scheme would do) and that the approximation loss is o(1). As written, the claimed optimal trade-off is not fully proved.
  2. [§5.2 (Algorithms 6 and 7) and §6.1 (Algorithm 10)] The same deferral to “standard techniques of [9]” appears in the implementation remarks for the guided and reduced-rate continuous greedy algorithms. For these algorithms the convexity arguments in Observations 5.7 and 6.3 do extend to straightforward Euler discretizations, preserving y(t)/t ∈ P, but the paper never states this explicitly. Since several stated infeasibility ratios, such as those in Theorems 6.1 and 6.6, are exact rather than asymptotic, the paper should include a short uniform statement of the discrete invariants and of the approximation error incurred by discretization.
minor comments (7)
  1. [Algorithm 2, line 1] The initialization “Let x(0) ← 0 and x(1) ← 1_N” appears to be a typo: the proof of Corollary 4.14 uses y(0) = 1_N, so the algorithm should initialize y(0) ← 1_N.
  2. [Lemma 4.13, Inequality (4)] The right-hand side of Inequality (4) appears to be missing a factor of 2; Inequality (5) and the subsequent algebra suggest the intended bound is 2·max{0, (a_u−ℓp_u)(b_u+ℓp_u)/(a_u+b_u)}.
  3. [Abstract and Observation 2.3] The abstract has “Bicrteria” instead of “Bicriteria”, and Observation 2.3 has “multinear” instead of “multilinear”.
  4. [Theorem 5.6] The statement “(1/2 − ε, O(ε−1)-bicriteria” is missing a closing parenthesis; it should read “(1/2 − ε, O(ε^{-1}))-bicriteria”.
  5. [Theorem 6.10] The infeasibility ratio for cardinality constraints is garbled as “⌈ln 1 2 ln(ε−1/2)⌉”; it should presumably be ⌈ 1/2 ln(ε^{-1/2})⌉.
  6. [Algorithm 4 and Section 4.3] The symbol c is used both for the density of the constraint and for the cost function in Algorithm 4; this dual use is confusing and should be disambiguated.
  7. [Throughout] There are several other typos (“cardnality” in §4.2, “monotnone” in §4.2.3, “constat” in Theorem 6.8, “symmrtric” in §6.3, “covex” in footnote 3); a careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the bicriteria trade-off is derived, not fitted, and the self-citations are real prior results that do not assume the target theorems.

full rationale

The central results of the paper, Theorems 4.6 and 4.7, are proved from stated definitions, explicit constructions, and independently published lemmas. The density-dependent infeasibility ratio rho(c, eps) is obtained by algebraically solving a differential-inequality analysis for Algorithm 2 and by a matching lower-bound construction; it is not fitted to data or defined so that the upper and lower bounds match by construction. The lower-bound instance in Section 4.2.2 is a novel explicit family of monotone submodular functions whose symmetry gap is analyzed directly, and the c > 1/2 hardness extends the prior work of Filmus et al. rather than importing a uniqueness theorem. The paper does rely on several results from the authors' own prior work, notably Measured Continuous Greedy [24], the symmetric submodular maximization algorithm [22], and DR-submodular tools [6,7]. These are machine-checkable or published theorems with stated assumptions that do not include the bicriteria results proved here, so they constitute real evidence rather than circular support. The discretization of the continuous algorithms, deferred to 'standard techniques of [9]', is an omitted implementation and potential correctness gap, especially for the variable-rate Continuous Double Greedy in Algorithm 2, but it is not a circularity: it concerns whether the 1-o(1) objective-loss discretization preserves the pointwise infeasibility bound, not whether a result is assumed through self-citation or by construction. No equation in the paper is equivalent to its input by definition, and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on the value oracle model, solvable and usually down-closed convex sets, rational density for cardinality constraints, and the standard continuous greedy framework with exact multilinear extension access. These are domain assumptions standard to submodular optimization, not hidden parameters fitted to data. No free parameters or invented entities appear.

assumptions (5)
  • domain assumption Value oracle access: algorithms know f only through queries f(S) for chosen S (Section 2, final remark).
    Essential for the lower bounds and standard in the field; guarantees are stated under this model.
  • domain assumption Solvable and down-closed convex sets: for most results, P is a down-closed solvable convex set, so linear optimization over P is efficient and coordinate-wise shrinking a feasible vector preserves feasibility (Sections 2.3, 5.2).
    Used to choose x(t) in continuous greedy and to bound infeasibility; Theorem 5.23 shows this is necessary for general submodular functions.
  • domain assumption Direct access to the multilinear extension F and its gradients in the analyses (Sections 4.2.1, 5.2.1, 6.1).
    Continuous-time algorithms are analyzed exactly; implementability is deferred to standard techniques of [9].
  • domain assumption Rational density c for cardinality constraints (c = h/ell for integers h, ell) and element costs at most the budget for knapsack constraints (Section 2.1, Theorem 4.7).
    The hard distribution in Section 4.2.2 uses a rational c; the knapsack restriction is WLOG and preserves OPT.
  • standard math Known external theorems: Measured Continuous Greedy guarantees [24], Double Greedy [8,6], symmetry gap transfer [46], and the hypergeometric tail bound [45] (Sections 2 and 5).
    These are cited published results used as black boxes; they are not rederived.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bicriteria Submodular Maximization." pith.science (2026). https://pith.science/paper/DTNDIZWT

@misc{pith2026250710248,
  author       = {Pith},
  title        = {Pith review of: Bicriteria Submodular Maximization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DTNDIZWT}},
  note         = {Machine review of arXiv:2507.10248}
}
read the original abstract

Submodular functions and their optimization have found applications in diverse settings ranging from machine learning and data mining to game theory and economics. In this work, we consider the constrained maximization of a submodular function, for which we conduct a principled study of bicriteria approximation algorithms -- algorithms which can violate the constraint, but only up to a bounded factor. Bicrteria optimization allows constrained submodular maximization to capture additional important settings, such as the well-studied submodular cover problem and optimization under soft constraints. We provide results that span both multiple types of constraints (cardinality, knapsack, matroid and convex set) and multiple classes of submodular functions (monotone, symmetric and general). For many of the cases considered, we provide optimal results. In other cases, our results improve over the state-of-the-art, sometimes even over the state-of-the-art for the special case of single-criterion (standard) optimization. Results of the last kind demonstrate that relaxing the feasibility constraint may give a perspective about the problem that is useful even if one only desires feasible solutions.

Figures

Figures reproduced from arXiv: 2507.10248 by the authors.

Figure 1
Figure 1. A plot of the approximation ratio achieved by Algorithm 9 vs. the infeasibility ratio [PITH_FULL_IMAGE:figures/full_fig_p057_1.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Submodular Maximization under Supermodular Constraint: Greedy Guarantees

    cs.DS 2026-02 conditional novelty 7.0 of 10

    A ratio-greedy algorithm gives a (1−e^{−(1−γ)}) approximation with bounded budget violation for submodular maximization under a supermodular constraint; the bound is tight for the algorithm.

Reference graph

Works this paper leans on

55 extracted references · 36 canonical work pages · cited by 1 Pith paper

  1. [9]

    Maximizing a monotone submodular function subject to a matroid constraint

    Gruia Calinescu, Chandra Chekuri, Martin P´ al, and Jan Vondr´ ak. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. , 40(6):1740–1766,

    work page

  2. [24]

    Combinatorial auctions via posted prices

    Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Piotr Indyk, editor, ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 123–

    work page

  3. [1]

    Buhmann, and Andreas Krause

    Andrew An Bian, Baharan Mirzasoleiman, Joachim M. Buhmann, and Andreas Krause. Guar- anteed non-convex optimization: Submodular maximization over continuous domains. In Aarti Singh and Xiaojin (Jerry) Zhu, editors, Proceedings of the International Conference on Arti- ficial Intelligence and Statistics (AISTATS) , volume 54 of Proceedings of Machine Learni...

    work page 2017

  4. [2]

    Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case

    Kobi Bodek and Moran Feldman. Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case. Algorithmica, 86:1080–1134, 2024. doi: 10.48550/arXiv.2204.03412

    work page Pith review arXiv doi:10.48550/arxiv.2204.03412 2024

  5. [3]

    Richard A. Brualdi. Comments on bases in dependence structures. Bull. of the Australian Math. Soc., 1(02):161–167, 1969

    work page 1969

  6. [4]

    Deterministic algorithms for submodular maximization problems

    Niv Buchbinder and Moran Feldman. Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms , 14(3):32:1–32:20, 2018. doi: 10.1145/3184990. URL https://doi.org/10.1145/3184990

    work page doi:10.1145/3184990 2018

  7. [5]

    Constrained submodular maximization via a nonsym- metric technique

    Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a nonsym- metric technique. Math. Oper. Res. , 44(3):988–1005, 2019. doi: 10.1287/MOOR.2018.0955. URL https://doi.org/10.1287/moor.2018.0955

    work page arXiv 2019

  8. [6]

    Constrained submodular maximization via new bounds for DR-submodular functions

    Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for DR-submodular functions. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Annual ACM Symposium on Theory of Computing (STOC) , pages 1820–1831. ACM, 2024. doi: 10.1145/3618260.3649630. URL https://doi.org/10.1145/3618260.3649630

    arXiv 2024

Show all 55 references
  1. [7]

    Submodular maximization with cardinality constraints

    Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth An- nual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1433–1452. SIAM, 2014. doi: 10.1137...

    2014 doi

  2. [8]

    A tight linear time (1/2)- approximation for unconstrained submodular maximization

    Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization. SIAM J. Comput. , 44(5):1384– 1402, 2015. doi: 10.1137/130929205. URL https://doi.org/10.1137/130929205

    2015 doi

  3. [10]

    Submodular function maximization via the multilinear relaxation and contention resolution schemes

    Chandra Chekuri, Jan Vondr´ ak, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. , 43(6): 1831–1879, 2014. doi: 10.1137/110839655. URL https://doi.org/10.1137/110839655

    2014 doi

  4. [11]

    The tail of the hypergeometric distribution

    Vaˇ sek Chv´ atal. The tail of the hypergeometric distribution. Discrete Mathematics , 25(3): 285–287, 1979

    1979

  5. [12]

    Scalable bicriteria algorithms for non-monotone submodular cover

    Victoria Crawford. Scalable bicriteria algorithms for non-monotone submodular cover. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, International Conference on Artificial Intelligence and Statistics (AISTATS) , volume 206 of Proceedings of Machine Learni...

    2023

  6. [13]

    Victoria G Crawford, Alan Kuhnle, and My T. Thai. Submodular Cost Submodular Cover with an Approximate Oracle. In Proceedings of the 36th International Conference on Machine Learning, volume PMLR 97, 2019

    2019

  7. [14]

    Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection

    Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Lise Getoor and Tobias Scheffer, editors, International Conference on Machine Learning (ICML), pages 1057–1064. Omnipress,

  8. [15]

    Communication complexity of combinatorial auctions with submodular valuations

    Shahar Dobzinski and Jan Vondr´ ak. Communication complexity of combinatorial auctions with submodular valuations. In Sanjeev Khanna, editor, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1205–1215. SIAM, 2013. doi: 10.1137/1.9781611973105.87. URL https://doi.org/10....

    2013 doi

  9. [16]

    URL https://icml.cc/2011/papers/542_icmlpaper.pdf

    2011

  10. [17]

    Elenberg, Alexandros G

    Ethan R. Elenberg, Alexandros G. Dimakis, Moran Feldman, and Amin Karbasi. Stream- ing weak submodularity: Interpreting neural networks on the fly. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vish- wanathan, and Roman Garnett, edi...

    2017

  11. [18]

    Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, and Anna R. Karlin. Combinatorial auctions with interdependent valuations: SOS to the rescue. Math. Oper. Res., 49(2):653–674,

  12. [19]

    The submodular welfare problem with demand queries

    Uriel Feige and Jan Vondr´ ak. The submodular welfare problem with demand queries. Theory Comput., 6(1):247–290, 2010. doi: 10.4086/TOC.2010.V006A011. URL https://doi.org/ 10.4086/toc.2010.v006a011

    2010 doi

  13. [20]

    Mirrokni, and Jan Vondr´ ak

    Uriel Feige, Vahab S. Mirrokni, and Jan Vondr´ ak. Maximizing non-monotone submodular functions. SIAM J. Comput. , 40(4):1133–1153, 2011. doi: 10.1137/090779346. URL https: //doi.org/10.1137/090779346. 71

    2011 doi

  14. [21]

    Alina Ene and Huy L. Nguyen. Constrained submodular maximization: Beyond 1/e. In Irit Dinur, editor, IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 248–257. IEEE Computer Society, 2016. doi: 10.1109/FOCS.2016.34. URL https: //doi.org/10.1109/FOCS.2016.34

    2016 doi

  15. [22]

    Maximizing symmetric submodular functions

    Moran Feldman. Maximizing symmetric submodular functions. ACM Trans. Algorithms , 13 (3):39:1–39:36, 2017. doi: 10.1145/3070685. URL https://doi.org/10.1145/3070685

    2017 doi

  16. [23]

    Guess free maximization of submodular and linear sums

    Moran Feldman. Guess free maximization of submodular and linear sums. Algorithmica, 83(3):853–878, 2021. doi: 10.1007/S00453-020-00757-9. URL https://doi.org/10.1007/ s00453-020-00757-9

    2021 doi

  17. [25]

    Yuval Filmus, Roy Schwartz, and Alexander V. Smal. Separating coverage and submodular: Maximization subject to a cardinality constraint. In Nicole Megow and Amitabh Basu, editors, International Conference on Integer Programming and Combinatorial Optimization (IPCO) , volume 15...

    2025 doi

  18. [26]

    Submodular maximization by simulated annealing

    Shayan Oveis Gharan and Jan Vondr´ ak. Submodular maximization by simulated annealing. In Dana Randall, editor, ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1098–

  19. [27]

    Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan, and Suresh Venkatasubramanian. On minimizing budget and time in influence propagation over social networks. Soc. Netw. Anal. Min. , 3(2):179–192, 2013. doi: 10.1007/S13278-012-0062-Z. URL https://doi.org/ 10.1007/s13278-012-0062-z

    2013 doi

  20. [28]

    A unified continuous greedy algorithm for submodular maximization

    Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Rafail Ostrovsky, editor, Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 570–579. IEEE Computer Society, 2011. d...

    2011 doi

  21. [29]

    Hochbaum

    Dorit S. Hochbaum. Approximation Algorithms for the Set Covering and Vertex Cover Prob- lems. SIAM Journal on Computing , 11(3):555–556, August 1982. ISSN 0097-5397, 1095-7111. doi: 10.1137/0211045

    1982 doi

  22. [30]

    Probability inequalities for sums of bounded random variables

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 1963

    1963

  23. [31]

    Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints

    Rishabh K Iyer and Jeff A Bilmes. Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints. In Advances in Neural Information Processing Systems , volume 26. Curran Associates, Inc., 2013

    2013

  24. [32]

    Uncon- strained submodular maximization with modular costs: Tight approximation and application to profit maximization

    Tianyuan Jin, Yu Yang, Renchi Yang, Jieming Shi, Keke Huang, and Xiaokui Xiao. Uncon- strained submodular maximization with modular costs: Tight approximation and application to profit maximization. Proceedings of the VLDB Endowment , 14(10):1756–1768, June 2021. ISSN 2150-809...

    2021

  25. [33]

    Submodular Maxi- mization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications

    Christopher Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. Submodular Maxi- mization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications. In Proceed- ings of the 36 Th International Conference on Machine Learning , volume PMLR 97, 2019

    2019

  26. [34]

    Submodular dictionary selection for sparse representation

    Andreas Krause and Volkan Cevher. Submodular dictionary selection for sparse representation. In Johannes F¨ urnkranz and Thorsten Joachims, editors,International Conference on Machine Learning (ICML), pages 567–574. Omnipress, 2010. URL https://icml.cc/Conferences/ 2010/papers/366.pdf

    2010

  27. [35]

    Approximations for monotone and nonmono- tone submodular maximization with knapsack constraints

    Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmono- tone submodular maximization with knapsack constraints. Math. Oper. Res. , 38(4):729–739,

  28. [36]

    Hui Lin and Jeff A. Bilmes. A class of submodular functions for document summarization. In Dekang Lin, Yuji Matsumoto, and Rada Mihalcea, editors, Annual Meeting of the As- sociation for Computational Linguistics: Human Language Technologies (ACL-HLT) , pages 510–520. The Asso...

    2011

  29. [37]

    Regularized nonmonotone submodular max- imization

    Cheng Lu, Wenguo Yang, and Suixiang Gao. Regularized nonmonotone submodular max- imization. Optimization, 73(6):1739–1765, June 2024. ISSN 0233-1934, 1029-4945. doi: 10.1080/02331934.2023.2173968

    2024

  30. [38]

    Regularized Submodular Maximization at Scale

    Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Regularized Submodular Maximization at Scale. In Proceedings of the 38 Th International Conference on Machine Learning, volume PMLR 139, 2021

    2021

  31. [39]

    Nemhauser, Laurence A

    George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approxi- mations for maximizing submodular set functions–I. Math. Programming, 14:265–294, 1978

    1978

  32. [40]

    Beyond 1/2-approximation for submodular maximization on massive data streams

    Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovic, Amir Zandieh, Aidasadat Mousavifar, and Ola Svensson. Beyond 1/2-approximation for submodular maximization on massive data streams. In Jennifer G. Dy and Andreas Krause, editors,International Conference on Machine Learni...

    2018

  33. [41]

    On maximizing sums of non-monotone submodular and linear functions

    Benjamin Qi. On maximizing sums of non-monotone submodular and linear functions. In Sang Won Bae and Heejin Park, editors, International Symposium on Algorithms and Compu- tation (ISAAC) , volume 248 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 41:1–41:...

    2022 doi

  34. [42]

    Schrijver

    A. Schrijver. Combinatorial Optimization: Polyhedra and Effciency . Springer-Verlag, Berlin, 2003

    2003

  35. [43]

    Combinatorial Optimization: Polyhedra and Efficiency

    Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency . Algorithms and Combinatorics. Springer Berlin, Heidelberg, 2003

    2003

  36. [44]

    Submodularity of influence in social networks: From local to global

    Elchanan Mossel and S´ ebastien Roch. Submodularity of influence in social networks: From local to global. SIAM J. Comput. , 39(6):2176–2188, 2010. doi: 10.1137/080714452. URL https://doi.org/10.1137/080714452

    2010 doi

  37. [45]

    Hypergeometric tail inequalities: ending the insanity

    Matthew Skala. Hypergeometric tail inequalities: ending the insanity. CoRR, abs/1311.5939, 2013

    2013 arXiv

  38. [46]

    Symmetry and approximability of submodular maximization problems

    Jan Vondr´ ak. Symmetry and approximability of submodular maximization problems. SIAM J. Comput., 42(1):265–304, 2013. doi: 10.1137/110832318. URL https://doi.org/10.1137/ 110832318

    2013 doi

  39. [47]

    Greedy approximations for min- imum submodular cover with submodular cost

    Peng-Jun Wan, Ding-Zhu Du, Panos Pardalos, and Weili Wu. Greedy approximations for min- imum submodular cover with submodular cost. Computational Optimization and Applications, 45(2):463–474, March 2010. ISSN 0926-6003, 1573-2894. doi: 10.1007/s10589-009-9269-y

    2010 doi

  40. [48]

    Efficient deterministic algorithms for maximizing symmetric submodular functions

    Zongqi Wan, Jialin Zhang, Xiaoming Sun, and Zhijie Zhang. Efficient deterministic algorithms for maximizing symmetric submodular functions. CoRR, abs/2406.14278, 2024. doi: 10.48550/ ARXIV.2406.14278. URL https://doi.org/10.48550/arXiv.2406.14278

    2024 doi arXiv

  41. [49]

    L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, December 1982. ISSN 0209-9683, 1439-6912. doi: 10.1007/ BF02579435. 74

    1982

  42. [50]

    Combinatorial Optimization: Polyhedra and Efficiency

    Alexander Shrijver. Combinatorial Optimization: Polyhedra and Efficiency . Springer, Berlin, Heidelberg, 2002. 73

    2002

  43. [135]

    doi: 10.1137/1.9781611973730.10

    SIAM, 2015. doi: 10.1137/1.9781611973730.10. URL https://doi.org/10.1137/1. 9781611973730.10

    2015 doi

  44. [1116]

    doi: 10.1137/1.9781611973082.83

    SIAM, 2011. doi: 10.1137/1.9781611973082.83. URL https://doi.org/10.1137/1. 9781611973082.83

    2011 doi

  45. [2011]

    URL https://doi.org/10.1137/080733991

    doi: 10.1137/080733991. URL https://doi.org/10.1137/080733991. 70

    doi

  46. [2013]

    URL https://doi.org/10.1287/moor.2013.0592

    doi: 10.1287/MOOR.2013.0592. URL https://doi.org/10.1287/moor.2013.0592

    2013

  47. [2024]

    URL https://doi.org/10.1287/moor.2023.1371

    doi: 10.1287/MOOR.2023.1371. URL https://doi.org/10.1287/moor.2023.1371

    2023

Pith tools

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