Pith. sign in

REVIEW 6 minor 29 references

Data-dependent Evaluations for Budgeted Submodular Maximization

T0 review · 0 major / 6 minor · reviewed 2026-07-08 · grok-4.5

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

Pith's one-line read New data-dependent upper bounds certify how close knapsack-constrained submodular solutions are to optimal.

desk verdict Clean knapsack extension of data-dependent dual bounds for submodular max; dominance holds and certificates tighten, novelty is incremental but real. read the letter →

arxiv 2607.05759 v1 pith:XNEL5GQW submitted 2026-07-07 cs.DS cs.AIcs.DM

Lejian Zhang , Xueyan Tang , Jing Tang This is my paper · ORCID
classification cs.DScs.AIcs.DM
keywords submodularmaximizationknapsackconstraintdata-dependentboundsapproximationcertificatesbudgetedoptimizationmonotonefunctions
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

Submodular maximization under a knapsack (budget) constraint is NP-hard, so algorithms usually only guarantee pessimistic worst-case approximation ratios that say little about any particular instance. This paper constructs new upper bounds on the optimal value that are computed from the same data the algorithm sees. The authors prove these bounds always sit above the true optimum and show, on real datasets, that they are tighter than earlier certificates, so a practitioner can finally read off a concrete gap between the solution just produced and the best possible value for that instance.

What carries the argument

Data-dependent upper-bound constructions that exploit the residual knapsack capacity and the marginal gains of remaining elements; once computed they dominate OPT and can be evaluated alongside any feasible solution to produce an instance-specific optimality gap.

What would settle it

On a concrete monotone submodular knapsack instance, compute both the new upper bound and a known better feasible value (or the true OPT via exhaustive search on a tiny instance); if the reported upper bound falls below that value, the dominance claim is false.

Watch

Extended reading notes

Core claim

The authors introduce data-dependent upper bounds for monotone submodular maximization under a single knapsack constraint; they prove each bound is always at least as large as OPT and demonstrate empirically that the resulting certificates of near-optimality are tighter than those obtained from prior techniques on real-world instances.

Load-bearing premise

The constructions remain valid upper bounds on OPT for general monotone submodular objectives under a single knapsack constraint without extra restrictions on costs or curvature.

Editorial extensions

If this is right

  • Any existing knapsack-constrained submodular algorithm can now report a concrete, instance-specific optimality gap instead of only a worst-case factor.
  • Practitioners can stop a greedy or local-search procedure once the data-dependent certificate shows the remaining gap is smaller than a chosen tolerance.
  • The same bounding technique supplies a practical way to compare different algorithms on the same data set by the tightness of the certificates they induce.
  • When the bound is tight, the produced solution is certified optimal without solving the NP-hard problem exactly.

Reading between the lines

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

  • The same residual-capacity idea could be adapted to produce data-dependent certificates for other packing constraints (matroids, multiple knapsacks) once the corresponding dual or residual arguments are written down.
  • If the bounds remain cheap to evaluate, they become natural early-stopping criteria inside large-scale streaming or distributed submodular pipelines.
  • A natural next measurement is how often the new certificates collapse the gap all the way to zero on typical ML feature-selection or summarization instances.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 6 minor

Summary. The manuscript studies monotone submodular maximization under a single knapsack (budget) constraint and proposes new data-dependent upper bounds on the optimal value OPT. It theoretically establishes that the proposed bounds are always valid upper bounds (they dominate OPT), and it empirically evaluates them as certificates of solution quality against prior approaches on real-world datasets, reporting tighter gaps between produced solutions and the certified upper bounds.

Significance. Worst-case approximation ratios for budgeted submodular maximization are often loose on concrete instances; instance-specific upper bounds that are guaranteed to dominate OPT are therefore practically useful for certifying solution quality in machine learning and data-mining applications. The paper’s combination of a proved dominance property and empirical evidence of tighter certificates is a genuine contribution if the constructions and proofs hold as claimed. The work is incremental rather than foundational, but it addresses a real evaluation gap in the literature and is of clear interest to the submodular-optimization community.

minor comments (6)
  1. The abstract asserts dominance and empirical advantages but does not preview the form of the bounds or the baselines. A one-sentence sketch of the construction (e.g., how the data-dependent terms are obtained from the ground set and costs) would help readers decide whether to continue.
  2. Ensure that every bound formula used in the experiments is stated explicitly in the main body (or a clearly referenced appendix) with the precise oracle and cost assumptions under which dominance is proved, so that the empirical tables can be audited against the theory without ambiguity.
  3. In the experimental section, report wall-clock overhead of computing the new upper bounds relative to the algorithms being certified; practitioners need to know whether the tighter certificates are free or expensive.
  4. Clarify notation for the knapsack capacity, element costs, and the submodular value oracle at first use, and keep the same symbols consistently in theorems, algorithms, and tables.
  5. If multiple prior data-dependent or dual-style bounds are used as baselines, cite them with precise references and state the exact variant implemented so that the reported gaps are reproducible.
  6. Minor copy-editing: check for consistency of hyphenation (“data-dependent” vs “data dependent”), and ensure all figures/tables are referenced in the text in order.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the constructive assessment. We appreciate the recognition that instance-specific upper bounds that dominate OPT are practically useful for certifying solution quality, and that our combination of a proved dominance property with empirical evidence of tighter certificates constitutes a genuine contribution of clear interest to the submodular-optimization community. The recommendation of minor revision is noted. The report as provided does not list specific major comments requiring changes; accordingly, we have not identified substantive technical revisions mandated by the referee. We remain ready to address any minor editorial or presentational suggestions from the referee or the editor in the next version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; data-dependent upper bounds are proved independently of certified solutions and are not fitted predictions.

full rationale

The paper's central claim is a family of data-dependent upper bounds on OPT for monotone submodular maximization under a single knapsack constraint, together with empirical certificates of solution quality. From the abstract and the load-bearing structure described, the bounds are theoretically proved to dominate OPT (always valid upper bounds) and are then used to measure how close a produced feasible solution is to optimal. A valid upper bound on OPT is independent of any particular candidate solution being certified; the gap certificate is therefore not forced by construction from the solution itself, nor is it a fitted parameter renamed as a prediction. No self-definitional loop (bound defined via the certified solution), no uniqueness theorem imported solely from the authors' prior work as an external fact, no ansatz smuggled via self-citation, and no renaming of a known empirical pattern appear in the claimed derivation. Empirical tables compare tightness against baselines on real-world datasets; such evaluation does not render the proved dominance circular. The derivation is therefore self-contained against the stated problem class, warranting score 0 with empty steps.

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

Abstract-only review: no free parameters, invented entities, or nonstandard axioms are visible. The work rests on the standard domain assumptions of submodular maximization under a knapsack constraint (set function submodularity, nonnegativity/monotonicity as usual in the literature, positive item costs, budget B). Any additional modeling choices in the bound construction are invisible without the body.

assumptions (3)
  • domain assumption Objective is a submodular set function (standard diminishing-returns property) evaluable by value oracle.
    Core setting of the paper; invoked throughout the problem statement in the abstract.
  • domain assumption Feasible sets are defined by a single linear knapsack (budget) constraint on nonnegative item costs.
    Defines the 'budgeted' problem class for which the new upper bounds are claimed.
  • standard math Standard combinatorial-optimization background: NP-hardness of exact submodular maximization under knapsack; existence of greedy/local-search approximation algorithms with known worst-case factors.
    Motivation for data-dependent certificates; assumed known rather than re-derived.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Data-dependent Evaluations for Budgeted Submodular Maximization." pith.science (2026). https://pith.science/paper/XNEL5GQW

@misc{pith2026260705759,
  author       = {Pith},
  title        = {Pith review of: Data-dependent Evaluations for Budgeted Submodular Maximization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XNEL5GQW}},
  note         = {Machine review of arXiv:2607.05759}
}
read the original abstract

Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.

Figures

Figures reproduced from arXiv: 2607.05759 by the authors.

Figure 1
Figure 1. Then, to fill up the budget b, we pick b ϵ slices. However, the element costs are not necessarily multiples of ϵ. Hence, it is possible for a slice to involve a number of elements, where the number is not fixed and the first as well as last elements may be partially involved. Note that all the elements involved in a slice would have successive indexes. In general, it would not guarantee that the maximum total value … view at source ↗
Figure 1
Figure 1. Naive slicing strategy 1 2 3 4 5 6 7 8 V\S Costs spent on elements selected c(1) c(4) s4 S [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 3
Figure 3. Actual approximation guarantee plots for different upper bounds [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Cutoff densities of elements in four datasets [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: Computational time plots for different upper bounds [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Actual approximation guarantee plots for different upper bounds in cost setting (b) [PITH_FULL_IMAGE:figures/full_fig_p025_6.png]
Figure 7
Figure 7. Figure 7: Actual approximation guarantee plots for different upper bounds in cost setting (c) [PITH_FULL_IMAGE:figures/full_fig_p026_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Information-theoretic feature selection via tensor decomposition and submodularity.IEEE Transactions on Signal Processing, 69:6195– 6205, 2021

    Magda Amiridi, Nikos Kargas, and Nicholas D Sidiropoulos. Information-theoretic feature selection via tensor decomposition and submodularity.IEEE Transactions on Signal Processing, 69:6195– 6205, 2021

    work page 2021

  2. [2]

    Fast algorithms for maximizing submodular functions

    Ashwinkumar Badanidiyuru and Jan V ondr´ak. Fast algorithms for maximizing submodular functions. InProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1497–1514. SIAM, 2014

    work page 2014

  3. [3]

    Instance specific approximations for submodular maximization

    Eric Balkanski, Sharon Qian, and Yaron Singer. Instance specific approximations for submodular maximization. InInternational Conference on Machine Learning, pages 609–618. PMLR, 2021

    work page 2021

  4. [4]

    Submodular feature selection for partial label learning

    Wei-Xuan Bao, Jun-Yi Hang, and Min-Ling Zhang. Submodular feature selection for partial label learning. InProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 26–34, 2022

    work page 2022

  5. [5]

    Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: https://doi.org/10.24432/C5XW20

    work page doi:10.24432/c5xw20 1996

  6. [6]

    The fast algorithm for submodular maximization

    Adam Breuer, Eric Balkanski, and Yaron Singer. The fast algorithm for submodular maximization. InInternational Conference on Machine Learning, pages 1134–1143. PMLR, 2020

    work page 2020

  7. [7]

    A Primal-Dual Analysis of Monotone Submodular Maximization

    Deeparnab Chakrabarty and Luc Cote. A primal-dual analysis of monotone submodular maximiza- tion.arXiv preprint arXiv:2311.07808, 2023

    work page Pith review arXiv 2023

  8. [8]

    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.arXiv preprint arXiv:1102.3975, 2011

    work page Pith review arXiv 2011

Show all 29 references
  1. [9]

    Revenue submodularity

    Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. Revenue submodularity. In Proceedings of the 10th ACM Conference on Electronic Commerce, pages 243–252, 2009

    2009

  2. [10]

    A threshold of ln n for approximating set cover.Journal of the ACM, 45(4):634–652, 1998

    Uriel Feige. A threshold of ln n for approximating set cover.Journal of the ACM, 45(4):634–652, 1998

    1998

  3. [11]

    Practical budgeted submodular maximization

    Moran Feldman, Zeev Nutov, and Elad Shoham. Practical budgeted submodular maximization. Algorithmica, 85:1332–1371, 2023

    2023

  4. [12]

    Budgeted nonparametric learning from data streams

    Ryan Gomes and Andreas Krause. Budgeted nonparametric learning from data streams. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 391–398, 2010

    2010

  5. [13]

    Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints

    Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. InInternational conference on machine learning, pages 2544–2553. PMLR, 2018

    2018

  6. [14]

    Maximizing the spread of influence through a social network

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

    2003

  7. [15]

    The budgeted maximum cov- erage problem.Information Processing Letters, 70(1):39–45, 1999

    Samir Khuller, Anna Moss, and Joseph (Seffi) Naor. The budgeted maximum cov- erage problem.Information Processing Letters, 70(1):39–45, 1999. URL: https: //www.sciencedirect.com/science/article/pii/S0020019099000319, doi: 10.1016/S0020-0190(99)00031-9

    1999 doi

  8. [16]

    Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies.Journal of Machine Learning Research, 9(2), 2008

    Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies.Journal of Machine Learning Research, 9(2), 2008

    2008

  9. [17]

    A refined analysis of submodular greedy.Opera- tions Research Letters, 49(4):507–514, 2021

    Ariel Kulik, Roy Schwartz, and Hadas Shachnai. A refined analysis of submodular greedy.Opera- tions Research Letters, 49(4):507–514, 2021

    2021

  10. [18]

    Cost-effective outbreak detection in networks

    Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. InProceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 420–429, 2007

    2007

  11. [19]

    SNAP Datasets: Stanford large network dataset collection

    Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014

    2014

  12. [20]

    Multi-document summarization via budgeted maximization of submodular functions

    Hui Lin and Jeff Bilmes. Multi-document summarization via budgeted maximization of submodular functions. InHuman Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 912–920, 2010

    2010

  13. [21]

    Leveraging sparsity for efficient submod- ular data summarization.Advances in Neural Information Processing Systems, 29, 2016

    Erik Lindgren, Shanshan Wu, and Alexandros G Dimakis. Leveraging sparsity for efficient submod- ular data summarization.Advances in Neural Information Processing Systems, 29, 2016

    2016

  14. [22]

    Nemhauser and Laurence A

    George L. Nemhauser and Laurence A. Wolsey. Best algorithms for approximating the maximum of a submodular set function.Mathematics of Operations Research, 3(3):177–188, 1978

    1978

  15. [23]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. InProceedings of the 29th AAAI Conference on Artificial Intelligence, pages 4292–4293, 2015. URL:https://networkrepository.com

    2015

  16. [24]

    A note on maximizing a submodular set function subject to a knapsack constraint

    Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43, 2004

    2004

  17. [25]

    Revisiting modified greedy algorithm for monotone submodular maximization with a knapsack constraint

    Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, and Junsong Yuan. Revisiting modified greedy algorithm for monotone submodular maximization with a knapsack constraint. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1–22, 2021

    2021

  18. [26]

    Online processing algorithms for influence maximization

    Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. Online processing algorithms for influence maximization. InProceedings of the 2018 ACM SIGMOD International Conference on Management of Data, pages 991–1005. ACM, 2018

    2018

  19. [27]

    Laurence A. Wolsey. Maximising real-valued submodular functions: Primal and dual heuristics for location problems.Mathematics of Operations Research, 7(3):410–425, 1982

    1982

  20. [28]

    bring your own greedy

    Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. “bring your own greedy”+max: near- optimal 1/2-approximations for submodular knapsack. InInternational Conference on Artificial Intelligence and Statistics, pages 3263–3274. PMLR, 2020. 18

    2020

  21. [29]

    Trajectory- driven influential billboard placement

    Ping Zhang, Zhifeng Bao, Yuchen Li, Guoliang Li, Yipeng Zhang, and Zhiyong Peng. Trajectory- driven influential billboard placement. InProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’18, page 2748–2757, New York, NY , USA,...

    2018 doi

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.