{"id":"58980f3e-c140-4ca7-9947-1b623d245db5","arxiv_id":"2505.13670","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A curvature-triggered rewiring step added to sequential greedy yields better empirical coverage values while preserving the (1 - 1/e) worst-case guarantee for monotone submodular maximization under a cardinality constraint.","lead":"This paper proposes ResQue Greedy, a modified sequential greedy algorithm for submodular maximization that occasionally removes a previously chosen element and reselects greedily, guided by a new 'set curvature' measure. In two coverage experiments it reports higher objective values than standard greedy at similar computational cost, while keeping the same worst-case guarantee.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed improvement rests on an unproven trigger law; set curvature is not monotone as the permissible set shrinks, so the trigger can fire for benign reasons, and the experiments lack statistical support.","rationale":"The reader's weakest assumption correctly identifies the trigger law as the load-bearing, unproven component. My reading sharpens this: the trigger compares curvatures over different permissible sets A_i, and Lemma 3.1's monotonicity requires a fixed A, so the heuristic signal can fire on benign shrinking of the candidate set. This makes the absence of a proof more than a gap; it is a concrete failure mode. The worst-case bound (Theorem 4.1) is standard and correct, and the complexity objection (exponential overhead claim) is actually an internal error that overstates cost, not a threat to the central claim. The empirical evidence is suggestive but not statistically validated, so the appropriate verdict remains CONDITIONAL. Since the reader already assigned CONDITIONAL, no adjustment is needed.","tokens_in":11909,"tokens_out":8270,"duration_ms":79617,"concrete_test":"Re-run the Table I Monte-Carlo simulation with an added control arm that triggers rewiring at uniformly random iterations with the same expected number of activations as the curvature trigger. Compare mean normalized coverage over the 100 environments with a paired bootstrap 95% CI. If the curvature trigger does not beat the random-trigger control by more than the CI width, the improvement is not attributable to the curvature signal.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that ResQue Greedy improves on standard greedy hinges entirely on the trigger law (Definition 4) and step-back policy (Definition 5). No theorem shows these rules improve the final solution: Theorem 4.2 is a conditional inequality with undefined notation (gamma_p(S|s) is not defined in Definition 3) and does not establish that the trigger satisfies it. The trigger's rationale is also questionable: set curvature gamma(S|A) from Definition 2 need not increase as S grows because A shrinks. Since gamma(S_i|A_i)=1-min_{e in A_i} Delta f(e|S_i)/f(e), removing the element that attains the minimum from A_i can raise the min and lower gamma. Thus gamma(S_i|A_i)<=gamma_e(S_i) can occur simply because the worst element was already selected, not because an earlier choice was harmful. The paper's own random-rewiring control (Table I: 0.7439 vs 0.7823) shows that rewiring without a reliable trigger degrades performance. The supporting experiments are two coverage problems with no error bars, significance tests, or comparisons to other algorithms, so the improvement is not statistically established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ResQue Greedy, a modification of the standard sequential greedy algorithm for monotone submodular maximization under a cardinality constraint. The algorithm adds a rewiring step: when a curvature-based trigger condition (Definition 4) fires, it removes one previously selected element according to a step-back policy (Definition 5) and performs an additional greedy selection. The paper claims that this procedure preserves the standard (1 - 1/e) worst-case approximation guarantee while empirically obtaining higher objective values than standard greedy on two coverage problems. Theorem 4.1 proves the worst-case bound for any trigger and step-back rule, and the argument in that proof is correct. The claimed improvement over greedy, however, rests on the heuristic trigger law and is not established theoretically; Theorem 4.2 is the only theoretical statement about improvement, and it has notational and logical problems. The experimental section provides two coverage examples with no error bars, significance tests, or comparison to standard submodular maximization baselines.","tokens_in":12147,"tokens_out":5232,"duration_ms":49519,"significance":"If the empirical improvement is real, the paper offers a simple, drop-in heuristic that preserves the standard worst-case guarantee and may improve solution quality in practice at modest computational cost. The idea of using local curvature as a trigger for rewiring is interesting and the preservation of the (1 - 1/e) bound for arbitrary trigger and removal rules is a useful robustness property. The theoretical contribution is otherwise modest: Theorem 4.1 reproduces the standard greedy bound, and no result in the paper proves that the proposed trigger law improves the final solution. The paper would be strengthened by releasing code and data, by reporting variance and significance statistics, and by clearly positioning the improvement claim as empirical rather than as a proven tighter bound.","major_comments":[{"comment":"Theorem 4.2 uses the undefined quantity γ_p(S^SG_{m-1} | s^SG_m). Definition 3 defines path curvature γ_p(S_i) only for a whole sequential construction, not for a set-element pair. In addition, the derived condition involves γ(S^RSG_{m-1} | A^SG_{m-1}), whereas the preceding calculation requires γ(S^RSG_{m-1} | {s^SG_m}). Since γ(S|A) ≥ γ(S|{e}) for any e in A, the displayed condition is merely sufficient, not necessary. The 'if and only if' claim is therefore not justified, and the proof also silently assumes that s^SG_m belongs to P \\ S^RSG_{m-1}, which may fail after a rewiring. This theorem needs to be restated with correct notation and a correct logical status.","section":"Section IV-B, Theorem 4.2"},{"comment":"The trigger law is the load-bearing component of the claimed improvement, but the paper gives no proof that the condition γ(S_i|A_i) ≤ γ_e(S_i) identifies elements whose removal raises the final objective. The motivating argument in Section IV-A assumes that γ(S_i|A_i) grows as elements are added, yet Lemma 3.1 is stated only for a fixed permissible set A; because A_i shrinks at each step, γ(S_i|A_i) can decrease simply because the element attaining the minimum marginal ratio has already been selected. The random-rewiring control in Table I shows that rewiring without an informative trigger can degrade performance, so the trigger law is not a cosmetic detail. The authors should either prove a property of the trigger law that relates it to the condition in Theorem 4.2 or substantially strengthen the empirical case.","section":"Section IV-A, Definition 4"},{"comment":"The experimental evidence does not statistically support the central claim. Table I reports averages over 100 Monte Carlo runs without error bars, confidence intervals, or significance tests, and Table II is a single instance. There is no comparison to standard baselines such as lazy greedy, local search, or a simple restart heuristic. Moreover, in Table II the random-rewiring greedy achieves 6,853 coverage versus 6,658 for standard greedy, which undermines the narrative that uninformed rewiring necessarily hurts performance. The improvement of ResQue Greedy over greedy needs to be demonstrated with variance statistics and, preferably, with multiple problem classes.","section":"Section V, Tables I and II"},{"comment":"The abstract and introduction claim that ResQue Greedy 'achieves tighter near-optimality bounds' than sequential greedy. As stated, this is not established: Theorem 4.1 gives exactly the standard (1 - 1/e) bound, and no theorem proves that the algorithm's solution value dominates that of standard greedy. The only support for the tightness claim is empirical. The paper should either prove a formal improvement condition that is actually satisfied by the trigger law, or explicitly reword the contribution as an empirically effective heuristic with a preserved worst-case guarantee.","section":"Abstract and Section I"}],"minor_comments":[{"comment":"The paper uses the term 'normal' for f but never states the normalization condition; it should explicitly say f(∅)=0.","section":"Section III, Definition 2"},{"comment":"There is a typo in the proof of part (b): 'γ(Sℓ|{ℓℓ+1})' should be 'γ(Sℓ|{s_{ℓ+1}})'.","section":"Lemma 3.2 proof"},{"comment":"The update rule in Eq. (12) uses A'_ℓ without defining it; please define the permissible set after a step-back.","section":"Section IV-B, Eq. (12)"},{"comment":"The 'Queries' column in Table II appears to report total value-query counts, but this is not stated; please clarify how queries are counted and consider reporting standard deviations for the Monte Carlo results.","section":"Section V, Table II"},{"comment":"The conclusion states that numerical experiments 'confirmed' the effectiveness of the method; given the lack of statistical tests, a softer formulation such as 'suggest' would be more appropriate.","section":"Conclusion"}],"recommendation":"major_revision","confidential_remarks":"The core worst-case guarantee (Theorem 4.1) is correct and easy to verify, and the rewiring idea is potentially useful. However, the paper's central claim of improvement depends on a heuristic trigger that is not theoretically justified, and the only theorem addressing improvement (Theorem 4.2) has undefined notation and an unsubstantiated 'if and only if' statement. The experiments are too thin to carry the claim on their own. I recommend major revision rather than rejection because the flaws appear fixable: correct Theorem 4.2, add a formal or at least carefully hedged status for the trigger law, and provide statistically sound experiments. If the authors are unwilling to soften the theoretical contribution, the paper may not meet the bar for this journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: ResQue Greedy is a simple, cheap modification of the standard greedy algorithm for submodular maximization under a cardinality constraint. The authors add a curvature-based trigger and a step-back/rewiring step, prove that the rewired version still has the classic (1-1/e) worst-case bound, and report noticeably higher objective values on two coverage problems. The catch is that the trigger is a heuristic with no supporting analysis, and there is a concrete reason to expect it to fire on benign events.\n\nThe algorithm itself is new as far as I know. I have not seen a step-back policy driven by set and expansion curvature in the submodular maximization literature, and the lattice/path framing is a genuinely different way to present greedy. Theorem 4.1 is correct: after a step-back, the new greedy choice has marginal gain at least that of the removed element, so the value does not drop, and the induction goes through. The worst-case guarantee is safe regardless of the trigger. The random-rewiring control in Table I is also a nice experimental idea, because it shows that naive rewiring can hurt.\n\nThe soft spots are real. The trigger law in Definition 4 is justified only by intuition. The stress-test concern about set curvature is valid: gamma(S|A) is monotone in S for fixed A, but A shrinks as greedy proceeds. The min over a smaller permissible set can go up, so gamma(S_i|A_i) <= gamma_e(S_i) can occur just because the element achieving the historical minimum was selected, not because an earlier choice was harmful. That is a plausible source of false positives. Theorem 4.2 does not fix this: the notation gamma_p(S^{SG}_{m-1} | s^{SG}_m) is not defined in Definition 3, and the claimed if-and-only-if condition is not shown to be satisfied by the trigger. It reads more like a restatement than a proof of superiority.\n\nThere is also a clear error in the complexity discussion: each rewiring costs O(n) additional queries, and with at most k possible triggers the total extra cost is O(kn), not exponential. That should be corrected. The experiments are suggestive but thin: no error bars, no significance tests, and no comparison to standard local search or lazy-greedy baselines. The reported gains are large, so I would not dismiss them, but I also cannot tell from the paper whether they are robust.\n\nWho is this for? Practitioners who want a cheap drop-in improvement over greedy and can tolerate an unproven trigger. Theorists will not find a new bound, because the only proven guarantee is the standard one.\n\nMy recommendation: send it to peer review, but require a fix of the complexity statement, a clear statement that the improvement is heuristic-only, and either a better-justified trigger or experiments with variance and a stronger baseline. It is not ready as is, but it deserves a serious referee.","headline":"A practical greedy tweak that keeps the standard worst-case bound, but the trigger that is supposed to make it better is unproven and the experiments lack statistical support.","tokens_in":12648,"tokens_out":4065,"would_cite":false,"duration_ms":39283,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"ResQue Greedy claims a local curvature trigger can steer sequential greedy to better solutions while keeping its worst-case guarantee.","keywords":["submodular maximization","sequential greedy algorithm","curvature","cardinality constraint","rewiring","set function","coverage maximization","lattice"],"falsifier":"One concrete test: on every monotone submodular instance over a small ground set (for example $|P| \\le 7$, enumerated exhaustively), run the ordinary greedy algorithm and ResQue Greedy and record every trigger firing; if any instance has a firing after which the final ResQue Greedy value is strictly below the ordinary greedy value, or a firing where deleting the element identified by the step-back policy and re-greedying yields no value gain at that stage, the claimed work of the trigger is not happening.","tokens_in":11656,"feed_emoji":"📡","tokens_out":10702,"duration_ms":98263,"temperature":0.7,"pith_summary":"The paper is trying to establish that a small, curvature-guided modification to the classic sequential greedy algorithm for maximizing a monotone submodular function under a cardinality constraint can produce higher-value solutions than ordinary greedy, while keeping the same worst-case approximation guarantee. The proposed method, Rewired Sequential Greedy (ResQue Greedy), treats the greedy construction as a path through the lattice of subsets, watches a local set-curvature statistic, and when an 'anomaly' is detected it removes the past element that most degraded future marginal gains and restarts the next greedy step from the reduced set. Theorem 4.1 preserves the standard $(1 - 1/e)$ guarantee for any choice of trigger and removal rule, and the reported experiments show higher coverage and feature counts with a modest increase in oracle queries. If the method works as claimed, it is an inexpensive drop-in improvement over one of the most widely used algorithms for resource allocation problems.","feed_headline":"Curvature trigger rewires greedy, lifting coverage by 13 percent","feed_subtitle":"A backtrack-and-retry step keeps greedy's worst-case bound while raising final objective value in coverage tests.","key_machinery":"The load-bearing object is the set curvature\n$$\\gamma(S \\mid A) = 1 - \\min_{e \\in A} \\frac{f(S \\cup \\{e\\}) - f(S)}{f(\\{e\\}) - f(\\emptyset)},$$\na local version of total curvature that quantifies how much adding elements from $A$ to the already-chosen set $S$ is worth relative to adding them to the empty set. Along a sequential construction it generates two running statistics: expansion curvature $\\gamma_e(S_i)$, the maximum set curvature encountered so far, and path curvature $\\gamma_p(S_i)$, the maximum curvature of the individual chosen elements. The mechanism that carries the argument is the pair of Definitions 4 and 5: the trigger law fires when $\\gamma(S_i \\mid A_i) \\le \\gamma_e(S_i)$, declaring that an earlier element has harmed the current expansion, and the step-back policy removes the element corresponding to the largest historical set curvature before running one more greedy iteration. Curvature is used as a cheap, query-free predictor of which past choices are worth undoing.","core_discovery":"On the paper's own terms, the discovery is that local curvature can be used online to correct the shortsightedness of sequential greedy. For a set $S$ and a permissible expansion $A$, set curvature $\\gamma(S \\mid A)$ measures how much marginal gains of elements in $A$ have already been diminished by the choice of $S$. Along the greedy path the paper tracks the expansion curvature $\\gamma_e(S_i)$, the maximum set curvature seen so far, and declares an anomaly at stage $i+1$ when $\\gamma(S_i \\mid A_i) \\le \\gamma_e(S_i)$, because a past element appears responsible for the erosion of future gains. The step-back policy then discards the element that produced that historical maximum and re-runs one greedy selection from the smaller set. Theorem 4.1 proves that Algorithm 2 retains the worst-case bound $f(S_{\\mathrm{RSG}}) \\ge (1 - 1/e)f(S^*)$ regardless of the trigger or step-back rule, and Theorem 4.2 gives an if-and-only-if path-curvature condition under which the rewired path stays at least as good as the ordinary greedy path. The two experiments report average normalized coverage rising from $0.7823$ for greedy to $0.8874$ for ResQue Greedy, and Mars features found rising from $6{,}658$ to $7{,}714$, while a random-rewiring control scores $0.7439$ and $6{,}853$, respectively.","pith_inferences":["One implication the authors leave implicit: the trigger compares curvatures but never checks whether the suspected element's actual marginal contribution at the current stage is small, so a variant that fires only when the gap $\\gamma_e(S_i) - \\gamma(S_i \\mid A_i)$ exceeds a tuned margin might buy larger gains per extra query.","Because a rewiring at the final step re-selects a best element from the reduced set, it cannot lower the value at that step; a cheaper variant that skips curvature monitoring and always performs one final re-greedy pass is a natural baseline the paper does not isolate.","The midpoint update for curvatures after a step-back, equation (12), is an approximation, so over multiple rewires the trigger's statistics drift from the true ones; tracking exact curvatures after each rewire would test whether the heuristic's performance degrades on long horizons."],"forward_implications":["Any instance that can be fed to sequential greedy can instead be passed to ResQue Greedy without losing the $(1 - 1/e)$ worst-case guarantee, since Theorem 4.1 holds for arbitrary later-stage trigger and step-back rules.","When the trigger fires rarely, the extra cost is one additional greedy pass per rewiring, so the method remains polynomial-time; in the two experiments it used roughly 14–18 percent more oracle queries than plain greedy.","Ordinary greedy is not a lower bound on the rewired path in general: the paper's random-rewiring control (0.7439 normalized coverage) lands below plain greedy (0.7823), so the curvature trigger, not the act of rewiring, is what must do the work.","For functions with low total curvature, the paper expects little gain because the trigger rarely fires; in such cases ResQue Greedy behaves essentially like sequential greedy."],"supporting_citations":[{"why":"Supplies the hardness result and the classical analysis of greedy for monotone submodular maximization that the paper modifies.","marker":"[5]"},{"why":"Defines total curvature and the $\\frac{1}{c}(1-e^{-c})$ bound that ResQue Greedy aims to beat in practice.","marker":"[6]"},{"why":"Shows the curvature-with-respect-to-optimal-set bound is tight for polynomial-time algorithms, motivating a local trigger instead of a global curvature parameter.","marker":"[7]"},{"why":"Provides the proof template for the standard $(1 - 1/e)$ greedy bound that Theorem 4.1 preserves for the rewired algorithm.","marker":"[13]"},{"why":"Underpins the claim that the coverage objective used in both experiments is monotone submodular.","marker":"[14]"},{"why":"Used to generate the varied-curvature ground sets in the Monte-Carlo sensor-deployment experiments.","marker":"[15]"},{"why":"Supplies the DoMars16k dataset of 132 deployment points and 16,150 features used in the second experiment.","marker":"[16]"}],"fun_headline_variants":["Curvature-aware rewiring boosts greedy coverage by 13%","ResQue Greedy rewires steps, fixing greedy's blind spots","Coverage jumps 13% when greedy backtracks on curvature","Curvature-metric trigger re-runs greedy, raising coverage","ResQue greedy: curvature feedback fixes suboptimal picks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the curvature trigger identifies past greedy choices whose removal improves the eventual solution; the paper motivates this with intuition but does not prove it, and the random-rewiring baseline shows that an uninformative trigger can make rewiring worse than plain greedy.","fun_headline_variants_meta":{"raw":{"variants":["Curvature-aware rewiring boosts greedy coverage by 13%","ResQue Greedy rewires steps, fixing greedy's blind spots","Coverage jumps 13% when greedy backtracks on curvature","Curvature-metric trigger re-runs greedy, raising coverage","ResQue greedy: curvature feedback fixes suboptimal picks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000798,"raw_usage":{"total_tokens":3516,"prompt_tokens":954,"completion_tokens":2562,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2473}},"tokens_in":570,"tokens_out":2562,"duration_ms":18451,"temperature":1.0,"reasoning_tokens":2473,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:12:17.448511+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One concrete test: on every monotone submodular instance over a small ground set (for example $|P| \\le 7$, enumerated exhaustively), run the ordinary greedy algorithm and ResQue Greedy and record every trigger firing; if any instance has a firing after which the final ResQue Greedy value is strictly below the ordinary greedy value, or a firing where deleting the element identified by the step-back policy and re-greedying yields no value gain at that stage, the claimed work of the trigger is not happening.","supporting_citations":[{"cited_title":"Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms),","cited_arxiv_id":null,"evidence_quote":"Shows the curvature-with-respect-to-optimal-set bound is tight for polynomial-time algorithms, motivating a local trigger instead of a global curvature parameter."},{"cited_title":"An exemplar-based approach to individualized parcellation reveals the need for sex specific functional networks,","cited_arxiv_id":null,"evidence_quote":"Underpins the claim that the coverage objective used in both experiments is monotone submodular."},{"cited_title":"Submodular Point Processes with Applications to Machine learning,","cited_arxiv_id":null,"evidence_quote":"Used to generate the varied-curvature ground sets in the Monte-Carlo sensor-deployment experiments."},{"cited_title":"Domars16k: A diverse dataset for weakly supervised geomorphologic analysis on mars,","cited_arxiv_id":null,"evidence_quote":"Supplies the DoMars16k dataset of 132 deployment points and 16,150 features used in the second experiment."}],"review_version":1}