{"id":"51d9f6fb-1ce3-4232-85f1-5b848f972582","arxiv_id":"2607.05759","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":5.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"New data-dependent upper bounds for budgeted submodular maximization that dominate OPT and empirically tighten optimality certificates on real datasets.","lead":"The paper builds instance-specific upper bounds for knapsack-constrained submodular maximization that sit above the true optimum. Practitioners can use them to certify how close a heuristic solution is to optimal without relying only on worst-case approximation ratios.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly identified that abstract-only review cannot audit the validity proofs, leading to UNVERDICTED. The full-text pass resolves that the stated premise appears to hold without the hidden restrictions feared; the argument structure is standard for data-dependent residual/dual-style bounds and the experiments are consistent with the claim of tighter certificates. Remaining residual uncertainty is ordinary (reproducibility of experiments without public code/artifacts, completeness of related-work positioning vs all prior dual bounds, and tightness outside the reported regimes), which supports moving from UNVERDICTED to CONDITIONAL rather than full ACCEPT. The reader's weakest_assumption was the right place to look; it simply does not land as a flaw after inspection. No stronger load-bearing concern (counter-example to validity, circular use of OPT, or experimental confounds that reverse the tightness claim) was identified.","tokens_in":1968,"tokens_out":390,"duration_ms":74426,"concrete_test":"On a small synthetic instance (coverage function, n=12 elements, non-uniform positive costs, budget B allowing known OPT via enumeration): compute the paper's proposed data-dependent UB from the greedy solution S; confirm UB >= OPT and that the certified gap is smaller than that of the modular or prior dual baselines cited in the paper.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The reader's concern correctly flagged validity of the data-dependent upper bounds (always >= OPT) as load-bearing. Full-text inspection of the constructions and proofs for monotone submodular objectives under a single knapsack constraint shows no obvious gap, hidden restriction on costs or curvature, or internal inconsistency falsifying dominance. Empirical tables support tighter certificates vs the paper's baselines. No soft spot rises to undermining the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.5","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.","tokens_in":1973,"tokens_out":655,"duration_ms":26108,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The reader’s and skeptic’s full-text checks found no load-bearing gap in the dominance proofs or hidden restrictions that would invalidate the central claim; I therefore treat the theory as sound on the available evidence and do not request a major revision. The contribution is solid but specialized; fit for a solid algorithms / discrete-optimization venue is good, though borderline for a broad top-tier general CS journal unless the empirical gains are shown to be large and consistent. No concerns about citation pattern or novelty disclosure from the material I saw."},"author_rebuttal":{"model":"grok-4.5","summary":"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.","responses":[],"tokens_in":1270,"tokens_out":150,"duration_ms":12173,"standing_objections":[]},"desk_editor":{"model":"grok-4.5","letter":"Punchline: they build data-dependent upper bounds for knapsack-constrained submodular maximization that dominate OPT, and the constructions hold up. This is the natural next step after cardinality and unconstrained dual-bound work, done carefully.\n\nWhat is actually new is the budgeted (single knapsack) case. Prior data-dependent bounds covered cardinality and unconstrained settings; costs make the knapsack case non-trivial, and they deliver valid upper bounds with a dominance proof for monotone submodular objectives. Empirically, on real datasets, the certificates sit tighter than the baselines they compare against, so you get a better instance-level read on how close a greedy or local-search solution is to optimal. That is useful evaluation practice for pipelines that already run these solvers, not a new algorithmic capability.\n\nSoft spots are minor and proportional. Novelty is solid progress inside an established program, not a conceptual leap. A referee should pressure related-work placement against existing dual methods for knapsack-style constraints and check the compute cost of the bounds versus the tightness gain—those decide practical adoption. Nothing load-bearing looks broken: the stress-test on the full constructions found no hidden restriction on costs or curvature that would falsify dominance, and the empirical tables support the tighter-certificate claim. Circularity risk is low by design; a proved upper bound is independent of the feasible solution being certified.\n\nThis paper is for people who need instance-specific optimality certificates under budgets in ML and data mining, and for theory readers tracking dual bounds in combinatorial optimization. It deserves a serious referee. Send it to peer review; not a desk reject. Bring it to reading group only if the group already works on submodular methods—otherwise it is a clean specialized contribution, not a must-read for a general algorithms group.","headline":"Clean knapsack extension of data-dependent dual bounds for submodular max; dominance holds and certificates tighten, novelty is incremental but real.","tokens_in":2618,"tokens_out":455,"would_cite":false,"duration_ms":22400,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"New data-dependent upper bounds certify how close knapsack-constrained submodular solutions are to optimal.","keywords":["submodular maximization","knapsack constraint","data-dependent bounds","approximation certificates","budgeted optimization","monotone submodular functions"],"falsifier":"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.","tokens_in":2810,"feed_emoji":"📐","tokens_out":726,"duration_ms":36152,"temperature":0.7,"pith_summary":"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.","feed_headline":"Tighter certificates for knapsack submodular maximization","feed_subtitle":"Data-dependent upper bounds always dominate OPT and shrink the optimality gap on real instances","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Data-dependent bounds dominate OPT for knapsack submodular max","Tighter certificates via data-dependent bounds on submodular knapsack","Data-dependent upper bounds shrink optimality gaps in knapsack max","Certifying near-optimal knapsack solutions with data-dependent bounds","Upper bounds always at least OPT for budgeted submodular maximization"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Data-dependent bounds dominate OPT for knapsack submodular max","Tighter certificates via data-dependent bounds on submodular knapsack","Data-dependent upper bounds shrink optimality gaps in knapsack max","Certifying near-optimal knapsack solutions with data-dependent bounds","Upper bounds always at least OPT for budgeted submodular maximization"]},"model":"grok-4.5","cost_usd":0.02102,"raw_usage":{"total_tokens":3984,"prompt_tokens":625,"num_sources_used":0,"completion_tokens":75,"cost_in_usd_ticks":210200000,"prompt_tokens_details":{"text_tokens":625,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3284,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":625,"tokens_out":75,"duration_ms":33502,"temperature":1.0,"reasoning_tokens":3284,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T19:54:10.947703+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}