{"id":"4521470e-4223-4770-942c-cc90e5d17d25","arxiv_id":"1908.00653","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The greedy algorithm for Submodular Cost Submodular Cover is shown to achieve new bicriteria approximation ratios when the benefit function is only accessible through an ϵ-approximate oracle, provided the smallest marginal gain exceeds a threshold.","lead":"This paper proves new approximation guarantees for greedy algorithms that solve a submodular covering problem when the true objective is too expensive to evaluate exactly and only a noisy approximation is available. The guarantees show that with enough separation between the error and the smallest marginal gain, the greedy solution is near-optimal in cost and nearly feasible.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Core theorems check out; the load-bearing gap is the case-study bridge: the Cohen et al. oracle's high-probability relative error converts to absolute error ε·τ per §1.3, and plugging ε_rel into the µ > 4εc_maxρ/c_min condition makes the reported ratios optimistic.","rationale":"Step-by-step verification: I re-derived the charging argument. In Appendix B, inequality (2) follows from |ΔF(A,x) − Δf(A,x)| ≤ 2ε for x ∈ {x_i, x̃_i} and the dominance of the F-greedy choice; (3) rearranges correctly; the error sum in (5) is bounded via the µ lower bounds and Σc(x_i) ≤ ρc(A); (6)-(8) telescope correctly using ω_i non-decreasing, which holds because x̃_i is the f-cost-effective maximizer and f is submodular; Eq. (9)-(10) bound the Δf(A,y)ω_k term via submodularity and the definition of x̃_k; Eq. (11)-(12) bound the charge using the integral trick with β ≤ π_{ℓ_y}(y) ≤ π_1(y) ≤ α. Theorem 2's m_y split is also sound: the prefix sum is bounded by c(y)(ln(α/λ) + 1) with the +1 absorbing the crossing term (π_{m_y} − π_{m_y+1})/π_{m_y} ≤ 1, and the tail is bounded by λρc(A)/µ since ω_i ≤ c(x_i)/Δf(A_{i-1},x_i) and π_i(y) ≤ λ for i > m_y. I therefore found no internal inconsistency in the central claim.\n\nThe concern that lands is the applicability bridge, and this is where I partially agree with the reader. The reader's weakest_assumption says the all-subsets deterministic bound is stronger than the sketch's per-query high-probability guarantee. My reading sharpens this: the proof only needs error control at the sets the greedy actually queries (the x̃_i sets are queried because every remaining element is evaluated), so a 'query-consistent' oracle model would suffice and would be closer to the Cohen et al. guarantee. The real obstructions are (a) the sketch's guarantee is high-probability, not deterministic, and the paper never accounts for the failure probability, and (b) the sketch's error is relative, so the absolute ε in the theorem's condition is ε_rel · sup_{queried} f ≈ ε_rel · τ, while §3's experiments appear to use ε_rel directly. Both obstructions are visible in the text: §1.3 states the relative-to-absolute conversion with an explicit upper bound B, and §3 states the query-based high-probability guarantee, yet the experimental section never carries the factor τ or a failure probability into the ratio formula. A single recalculation with ε_abs = ε·τ would settle whether the µ condition survives; if it does not, the plotted ratios and the abstract's 'empirically relevant' claim are not supported for the motivating oracle.\n\nI also note the experimental presentation issues the reader flagged (runs where the condition fails or the ratio exceeds 140 are omitted; no error bars), which are real but secondary. The alternative Theorem 1 in Appendix A.2 and Proposition 2 in Appendix A are correct as far as I can tell.\n\nBecause the theorems are correct and the gap is confined to the case-study bridge, the reader's CONDITIONAL verdict remains appropriate; my stress-test does not change it.","tokens_in":19963,"tokens_out":36673,"duration_ms":306228,"concrete_test":"Use a plotted run (e.g., Facebook, the largest threshold shown at a given ε). First, recover the sketch parameter k and check whether k = cε^{−2} log n (relative-error calibration). If so, recompute the Theorem 1 ratio r1 and the condition µ > 4εc_maxρ/c_min with ε_abs = ε·τ (the paper's own §1.3 conversion, B = τ), using the run's recorded µ, α, β, ρ, c_max/c_min. If the condition fails, or r1 changes by more than 20%, the plotted ε is not the absolute error the sketch delivers. Second, to test the deterministic/query-consistent assumption directly, instantiate ~20 independent Cohen et al. sketches with that k, run greedy with each, and record max over all queried sets X of |F(X) − f(X)|; compare this empirical maximum to ε and to ε·τ. If the empirical max exceeds ε (or exceeds ε·τ where the theorem requires ε), the case study does not satisfy the theorem's oracle hypothesis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorems 1 and 2 is sound: the Wan et al. charging argument is adapted correctly to the f-greedy sequence x̃_i, the monotonicity of ω_i uses submodularity of f, the error terms in Appendix B Eq. (5) are bounded with Δf(A_{i-1},x_i) ≥ µ and Δf(A_{i-1},x̃_i) ≥ (c_min/c_max)µ, and the truncation f = min{f,τ} preserves ε-approximation while ensuring f(A_k) ≤ τ = f(A*), so the link Σ_{j=i}^k Δf(A_{j-1},x_j) ≤ Σ_{y∈A*} π_i(y) holds even when f(A_k) < τ. I found no internal inconsistency.\n\nThe load-bearing weakness is the bridge from the theorem's hypothesis to the Section 3 case study. The theorems require |f(X) − F(X)| ≤ ε for all X ⊆ S, a deterministic uniform absolute-error bound. Section 3 states that with k = cε^{−2} log n, the Cohen et al. sketch has 'relative error of all queries over the duration of the greedy algorithm ... within ε with probability at least 1 − 1/n^{c−2}' — a high-probability, relative-error, query-based guarantee. To reach the theorem's hypothesis one needs: (i) high-probability → deterministic, and (ii) relative → absolute, which §1.3 itself performs by multiplying by an upper bound B on f, taken as τ. Notably, the proof's error-control sets A_{i-1}, A_{i-1}∪{x_i}, A_{i-1}∪{x̃_i}, A are all among the algorithm's queries (it evaluates every remaining element at each step), so the all-subsets condition is stronger than necessary; a query-consistent oracle model would suffice. But even that weaker model requires the ε·τ conversion and a deterministic (or failure-probability-accounted) bound. If the experiments set k = cε^{−2} log n with ε the plotted value and then use that same ε in the ratio formulas, the condition µ > 4εc_maxρ/c_min is optimistic by a factor of τ, and the plotted ratios are not certified by the sketch's actual guarantee. The theorems themselves are not invalidated, but the abstract's claim that the ratios are 'empirically relevant' for this motivating oracle is not yet demonstrated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Submodular Cost Submodular Cover (SCSC) problem, in which a monotone submodular benefit function f must be driven above a threshold τ while minimizing a monotone submodular cost c, under the assumption that the algorithm has access only to an ε-approximate surrogate F rather than to f. The authors analyze the natural greedy algorithm (Algorithm 1), which uses the truncated surrogate Fτ = min(F, τ). Theorem 1 gives a bicriteria guarantee: if the minimum greedy marginal gain µ satisfies µ > 4εc_maxρ/c_min, then the returned set A has f(A) ≥ τ−ε and c(A) ≤ ρ/(1−4εc_maxρ/(c_minµ)) · (ln(α/β)+2) · c(A*), where A* is optimal, α is the largest singleton value of f, β is the smallest nonzero marginal gain, and ρ is the curvature of c. Theorem 2 gives an incomparable bound that replaces β by a tunable parameter γ. The proofs adapt the charging argument of Wan et al. to the sequence of f-optimal augmentations x̃_i, and the paper includes a proof that the two bounds are incomparable. Section 3 presents a case study for the Influence Threshold problem using the Cohen et al. average-reachability sketch as the surrogate, proves that this sketch is non-submodular, and reports computed values of the two ratios on Facebook and GrQc networks.","tokens_in":20273,"tokens_out":15445,"duration_ms":122313,"significance":"If the oracle hypothesis of Theorems 1 and 2 is satisfied, the paper provides the first approximation guarantees for SCSC under a general approximate oracle, and the zero-error limit nearly recovers existing SCSC ratios. The charging argument is a genuine extension of Wan et al.: the lower bound on Δf(A_{i-1}, x̃_i), the monotonicity of the charges ω_i, and the telescoping bound in the proofs of Theorems 1 and 2 all check out. I found no internal inconsistency in the main derivation. The paper also gives an explicit feasibility loss of τ−ε and a clean demonstration that its two bounds are incomparable. However, the practical significance claimed through the Section 3 case study is not yet established, because the oracle used there does not satisfy the deterministic all-subsets absolute-error condition assumed by the theorems. Since the main theoretical results are sound and the gap is localized to the bridge between the oracle model and the case study, the manuscript is promising but needs revision.","major_comments":[{"comment":"The case study does not instantiate the hypothesis of Theorems 1 and 2. The theorems require |f(X) − F(X)| ≤ ε for every X ⊆ S, deterministically. The Cohen et al. oracle is described in Section 3 as having \"relative error of all queries over the duration of the greedy algorithm ... within ε with probability at least 1 − 1/n^{c−2}\", which is a high-probability, query-dependent, relative-error guarantee. The conversion in Section 1.3 from relative to absolute error uses B = τ as an upper bound on f \"over the duration of Algorithm 1\", but this is not justified: sets such as an optimal solution A* can have f(A*) ≥ τ, and the sketch estimates f, not the truncated function fτ. Truncating f and F after the fact does not preserve a relative-error guarantee for the sketch. Consequently, the ratios r1 and r2 plotted in Figures 3 and 4 are not proven approximation ratios for those runs. The authors should either prove a version of Theorems 1 and 2 under a high-probability per-query relative-error oracle (noting that the proof only queries sets of the form A_{i-1}, A_{i-1} ∪ {x}, A_{i-1} ∪ {x̃_i}, and the final A, so a union bound over polynomially many queries is feasible), or explicitly present the experiments as a heuristic illustration rather than an instantiation of the theorems.","section":"Section 3 and §1.3"},{"comment":"The proof of Theorem 1 (Alternative) contains an unjustified inequality. The proof states that for all x, ΔF(A, x) ≤ c(x)/c(x_k) · ΔF(A, x_k) ≤ (c_max/c_min)µ*, but Algorithm 1 selects x_k by maximizing ΔFτ(A, x)/c(x), not ΔF(A, x)/c(x). When F(A ∪ {x}) crosses the threshold τ, ΔFτ is at most τ − F(A), while ΔF(A, x) can be much larger. The subsequent conclusion that Δf(A, x) ≤ (c_max/c_min)µ* + 2ε for all x therefore does not follow as written. The theorem may be salvageable by splitting into the case where some remaining element crosses τ and the case where none does, but the proof is incomplete in its current form.","section":"Appendix A.2"}],"minor_comments":[{"comment":"The procedure for computing the upper bound on the Theorem 2 ratio from F alone is under-specified. The text says α and µ are bounded using F, but it does not give the exact formulas; for reproducibility the authors should state, for example, that α ≤ max_x(F({x}) + ε) and that µ can be lower bounded from the F-marginals of the chosen elements, together with the γ-selection rule used in the experiments.","section":"Section 3 and Appendix D"},{"comment":"The discussion states that the curvature ρ of c is assumed to be computable, but for a general monotone submodular cost function curvature is defined as a maximum over exponentially many subsets. The experiments use modular costs (ρ = 1) or manually chosen curvature values; the paper should at least note that computing ρ exactly is nontrivial in general.","section":"Section 2.1"},{"comment":"The definition of µ as min{fτ(A_i) − fτ(A_{i−1}) : i ∈ {1,...,k}} is not meaningful when k = 0; the proof handles k = 0 separately, but the definition and theorem statements should be adjusted to avoid an undefined quantity in the empty case.","section":"Section 1.3"},{"comment":"The experimental plots omit runs where the minimum marginal gain is too small relative to ε, and the text notes this. It would be helpful to state how many runs were omitted for each threshold, since the plotted values are conditional on the theorem condition and do not by themselves establish that the ratios are achievable at those thresholds.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"The main theorems appear correct and are a meaningful contribution. The principal risk is not the internal proofs but the mismatch between the theorem's deterministic all-subsets absolute-error hypothesis and the probabilistic per-query relative-error guarantee of the Cohen et al. sketch used in the experiments. If the authors can close this gap, or alternatively reposition the case study as heuristic, the paper would be a solid contribution. The flawed inequality in the Appendix A.2 alternative theorem also needs to be fixed, although it is an auxiliary result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead Crawford, Kuhnle, and Thai on SCSC with an approximate oracle. Bottom line: the core theory is sound and worth refereeing. The two approximation ratios for greedy with an absolute-error oracle are new, and the ε=0 version of Theorem 2 is a genuinely new bound for SCSC. The charging argument is a careful adaptation of Wan et al., with enough detail to check: the error-term bound, the µ > 4εcmaxρ/cmin condition, and the telescoping charge all hold. I did not find a hole in the proofs.\n\nWhat is genuinely useful: exact value oracles for SCSC are often #P-hard, so a general approximate-oracle analysis is the right problem. The second theorem, replacing the hard-to-bound β with a tunable γ, is a practical touch.\n\nSoft spots, in proportion. The experimental section overclaims. The plots omit runs where the µ condition fails or the ratio exceeds 140, and there are no error bars. That alone would be minor. The deeper issue is the bridge to the Cohen et al. reachability sketch. The theorems require a deterministic uniform absolute error |f(X)-F(X)| ≤ ε for all X. The sketch gives a high-probability relative-error guarantee on the greedy queries. To connect them, one must choose an absolute ε (multiply by an upper bound like τ) and account for failure probability. The paper gestures at this conversion in §1.3, but the case study appears to plug the relative ε from k = cε^{-2} log n directly into the ratio formulas. If so, the condition µ > 4εcmaxρ/cmin is too optimistic by roughly a factor of τ, and the plotted ratios are not certified by the sketch's guarantee. This does not touch the theorems, but it does mean the claim that the ratios take on \"empirically relevant values\" is not yet demonstrated for this motivating oracle. A query-consistent oracle model would be weaker than all-subsets, but it still needs the ε·τ conversion and a deterministic or failure-accounted bound.\n\nRecommendation: send to peer review. The theory is a solid contribution; the case study needs to be reworked or explicitly reframed as illustrative only. The authors should report the conversion, show the actual ε_abs used, and include variance or at least all runs.","headline":"Sound theory for SCSC with approximate oracles; the case-study bridge from relative-error sketch to absolute-error theorem needs fixing before the empirical claims are credible.","tokens_in":21020,"tokens_out":2361,"would_cite":true,"duration_ms":22734,"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":"The paper proves that the greedy algorithm for submodular cover keeps bounded approximation ratios when the benefit function is known only through an approximate, possibly non-submodular oracle.","keywords":["submodular cover","approximate oracle","greedy algorithm","approximation ratio","submodular cost","influence threshold","reachability sketch","curvature"],"falsifier":"Construct a small SCSC instance that satisfies $\\mu > 4\\epsilon c_{\\max}\\rho / c_{\\min}$ and run Algorithm 1 with an $\\epsilon$-approximate but non-submodular surrogate $F$; because every constant in the theorems is explicit, checking whether the output violates $f(A) \\ge \\tau - \\epsilon$ or exceeds the stated cost ratio would settle whether the guarantees are tight, and a search over adversarial $\\pm\\epsilon$ perturbations of a submodular $f$ could reveal whether the uniform-error condition is genuinely necessary.","tokens_in":19642,"feed_emoji":"📈","tokens_out":10265,"duration_ms":88277,"temperature":0.7,"pith_summary":"The paper asks whether the greedy algorithm for Submodular Cost Submodular Cover (SCSC) still has provable guarantees when the benefit function cannot be evaluated exactly and is replaced by an $\\epsilon$-approximate surrogate $F$. It establishes that, provided every element added by the greedy run has marginal benefit $\\mu$ large enough relative to $\\epsilon$, the greedy output covers the threshold up to a small loss, $f(A) \\ge \\tau - \\epsilon$, and its cost is bounded by a ratio that degrades gracefully with $\\epsilon$. This matters because in applications such as influence maximization the exact benefit is hard to compute, so optimization must run against sketches, simulations, or noisy learned surrogates that need not even be submodular. The two ratios established are incomparable: one is closer to the classical bounds but needs an exact-oracle quantity to evaluate; the other replaces that quantity with a tunable parameter and is computable from the surrogate alone.","feed_headline":"Approximate oracle still guarantees near-optimal submodular cover","feed_subtitle":"Two new bounds keep greedy's ratio under approximate oracles, losing only epsilon of the threshold.","key_machinery":"The load-bearing device is a charging argument that assigns the cost of the greedy solution to elements of the optimal solution, adapted from the integral-valued SCSC analysis of Wan et al. (2010). Because the surrogate $F$ may be non-submodular, the greedy elements $x_i$ need not exhibit diminishing cost-effectiveness, so the proof charges instead with $\\tilde{x}_i$, the element that would be most cost-effective according to the true function $f$ at the same step. These $\\tilde{x}_i$ have non-increasing marginal cost-effectiveness, which is exactly what the charge bound needs; the oracle error $\\epsilon$ enters as an additive distortion that is absorbed using the condition $\\mu > 4\\epsilon c_{\\max}\\rho / c_{\\min}$. In Theorem 2 the charge is truncated once marginal contributions fall below a level $\\lambda = \\gamma\\mu/(n\\rho)$, which trades the instance-dependent $\\beta$ for the tunable $\\gamma$ and makes the ratio computable from $F$ alone.","core_discovery":"The central claim is that Algorithm 1, the greedy rule that repeatedly adds the element maximizing $F_\\tau$-marginal gain per unit cost, is a bicriteria approximation algorithm for SCSC under an $\\epsilon$-approximate oracle. In Theorem 1, whenever the smallest marginal gain $\\mu$ of an added element satisfies $\\mu > 4\\epsilon c_{\\max}\\rho / c_{\\min}$, the returned set satisfies $f(A) \\ge \\tau - \\epsilon$ and $c(A) \\le \\frac{\\rho}{1 - 4\\epsilon c_{\\max}\\rho/(c_{\\min}\\mu)} (\\ln(\\alpha/\\beta) + 2) c(A^*)$, where $A^*$ is an optimal solution. Theorem 2 replaces $\\beta$ by a tunable $\\gamma \\in (0, 1 - 4\\epsilon c_{\\max}\\rho/(c_{\\min}\\mu))$ and gives $c(A) \\le \\frac{\\rho}{1 - 4\\epsilon c_{\\max}\\rho/(c_{\\min}\\mu) - \\gamma} (\\ln(n\\alpha\\rho/(\\gamma\\mu)) + 2) c(A^*)$, again with $f(A) \\ge \\tau - \\epsilon$. When $\\epsilon = 0$ the guarantees reduce, up to a small additive constant, to existing SCSC ratios, and the same charging framework yields a new exact-oracle ratio in the second case. The authors also show that the two ratios are incomparable, and that the Cohen et al. average-reachability sketch used in the case study is not submodular, so the general approximate-oracle analysis is not vacuous for that oracle.","pith_inferences":["The requirement that $F$ be uniformly $\\epsilon$-approximate on all subsets is stricter than the high-probability, query-dependent guarantee of many sketches; a natural extension is to prove versions of Theorems 1 and 2 that hold with high probability over the oracle's randomness using only the queries actually made.","The explicit dependence on $\\epsilon/\\mu$ suggests an adaptive scheme: increase sketch quality, or switch to exact evaluation, whenever marginal gains drop toward $4\\epsilon c_{\\max}\\rho / c_{\\min}$, preserving the ratio while saving computation early in the run.","The threshold $\\mu > 4\\epsilon c_{\\max}\\rho / c_{\\min}$ hints at an inherent limitation: for instances where every feasible set contains only elements with small marginal gains, no amount of greedy tuning can satisfy the condition, and a different algorithmic approach would be needed.","The incomparability of the two bounds mirrors a trade-off between tightness and evaluability; one could interpolate between $\\alpha/\\beta$ and $n\\alpha\\rho/(\\gamma\\mu)$ to design a family of ratios with adjustable computational cost."],"forward_implications":["If the theorems hold, SCSC admits bicriteria guarantees under sketches, simulations, and noisy learned surrogates, not just exact value oracles: the feasibility loss is only $\\epsilon$, not a constant fraction of the threshold.","With an exact oracle ($\\epsilon = 0$), the first bound becomes $\\rho(\\ln(\\alpha/\\beta) + 2)$, reproducing known SCSC ratios up to a small constant, while the second is a new incomparable exact-oracle ratio.","The condition $\\mu > 4\\epsilon c_{\\max}\\rho / c_{\\min}$ gives a quantitative prescription: an instance is amenable to greedy whenever the smallest marginal gain of chosen elements stays large relative to the oracle error and the cost curvature.","For influence threshold problems, the average-reachability sketch of Cohen et al. can serve as the oracle; the empirical case study shows the two ratios take moderate values on real networks even though the sketch is non-submodular.","Because Theorem 2's ratio is computable from $F$ alone, it can be evaluated online during a greedy run, making the guarantee usable even when the true benefit function cannot be queried."],"supporting_citations":[{"why":"Supplies the charging argument over elements of the optimal solution that the proofs of Theorems 1 and 2 adapt to the approximate-oracle setting.","marker":"Wan et al. (2010)"},{"why":"Establishes the classical greedy ratio for submodular cover with modular cost, the baseline the new bounds reduce to when $\\epsilon = 0$.","marker":"Wolsey (1982)"},{"why":"Gives the closest prior SCSC ratio, which Theorem 1's exact-oracle reduction is compared against.","marker":"Soma and Yoshida (2015)"},{"why":"Provides the approximate average-reachability sketch used as the non-submodular oracle in the influence threshold case study, together with its relative-error guarantee.","marker":"Cohen et al. (2014)"},{"why":"Defines the independent cascade influence model and the simulation-based reachability criterion that the case study's benefit function approximates.","marker":"Kempe et al. (2003)"},{"why":"Connects SCSC to submodular knapsack bicriteria guarantees; the paper contrasts its feasibility loss $\\tau - \\epsilon$ with the fraction $(1-1/e)\\tau$ available through that reduction.","marker":"Iyer and Bilmes (2013)"},{"why":"Analyzes submodular maximization with approximate oracles, the closest prior oracle-error setting and one the paper distinguishes from SCSC with general submodular cost.","marker":"Horel and Singer (2016)"}],"fun_headline_variants":["Greedy survives approximate oracle in submodular cover","Approximate oracle: greedy still near-optimal","Submodular cover with approximate oracle: two bounds","Near-optimal cover despite approximate oracle","Bicriteria guarantee for submodular cover with approximate oracle"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the surrogate function is within $\\epsilon$ of the true benefit function for every possible set, not just for the sets the greedy algorithm actually evaluates; many practical oracles, including the influence sketch used in the case study, only offer high-probability relative error on the queries made, so the uniform bound is a stronger property than the oracle delivers.","fun_headline_variants_meta":{"raw":{"variants":["Greedy survives approximate oracle in submodular cover","Approximate oracle: greedy still near-optimal","Submodular cover with approximate oracle: two bounds","Near-optimal cover despite approximate oracle","Bicriteria guarantee for submodular cover with approximate oracle"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001021,"raw_usage":{"total_tokens":4323,"prompt_tokens":979,"completion_tokens":3344,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":3279}},"tokens_in":595,"tokens_out":3344,"duration_ms":21628,"temperature":1.0,"reasoning_tokens":3279,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:42:20.639999+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small SCSC instance that satisfies $\\mu > 4\\epsilon c_{\\max}\\rho / c_{\\min}$ and run Algorithm 1 with an $\\epsilon$-approximate but non-submodular surrogate $F$; because every constant in the theorems is explicit, checking whether the output violates $f(A) \\ge \\tau - \\epsilon$ or exceeds the stated cost ratio would settle whether the guarantees are tight, and a search over adversarial $\\pm\\epsilon$ perturbations of a submodular $f$ could reveal whether the uniform-error condition is genuinely necessary.","supporting_citations":[],"review_version":1}