{"id":"5d14674d-70d2-4af2-95ed-790884bf5f1f","arxiv_id":"1908.01029","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"An evolutionary algorithm EASC achieves a constant bicriteria approximation for Minimum Cost Submodular Cover in expected polynomial time, matching greedy's guarantee while showing practical speedups.","lead":"The paper presents EASC, an evolutionary algorithm for minimum cost submodular cover, and proves it reaches a constant bicriteria approximation in expected polynomial time. It is the first evolutionary algorithm with a polynomial-time worst-case guarantee for this problem, and it beats the greedy baseline in experiments.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Bin index r=log_δ(ε) is non-integer for generic δ,ε; the algorithm and Theorem 1 depend on δ^r=ε, so the bin function and proof are not well-defined as written.","rationale":"The strongest claim is Theorem 1; for it to hold, the bin function must be a total, well-defined map from 2^S to {0,...,r} with δ^r=ε, and every step of the invariant argument must go through. The invariant argument is otherwise careful and self-contained: Lemma 1 and Lemma 2 are standard and correctly proven; Part One shows cost-effective solutions are never replaced by worse ones; Part Two uses δ≥1−cmin/c(A*) to force a bin increase; Part Three's four cases are algebraically sound when the final bin is exactly the (1−ε)τ threshold; Part Five's waiting-time bound is standard. I therefore do not see a falsehood in the central theorem. The weak point is formal: for generic real δ and ε, r=log_δ(ε) is not an integer, so 'bin i for i∈{0,...,r−1}' and 'bin r' do not define a partition. The proof's use of bin a+1 and of the final bin at (1−ε)τ presumes δ^r=ε exactly; with a ceiling, the top interval overlaps the final bin absent a priority rule, and with a floor there are uncovered f-values. This makes Algorithm 1 and Theorem 1 formally undefined for generic inputs. The reader's flagged δ-dependence is not the main problem: δ=1−cmin/c(S) is always an admissible instantiation since c(S) is an upper bound on c(A*) with B≤c(S), so the parameter can be set without knowing A*. I recommend keeping the CONDITIONAL verdict, with the condition expanded to include a corrected, unambiguous bin definition.","tokens_in":11823,"tokens_out":26349,"duration_ms":260067,"concrete_test":"Re-define the bin function as r=ceil(log_δ ε), B_r={X: fτ(X)≥(1−ε)τ} with final-bin priority, and B_i={X: (1−δ^i)τ≤fτ(X)<min((1−δ^{i+1})τ,(1−ε)τ)} for i<r; then re-run the proof of Theorem 1, especially Part Two and Case (iii) of Part Three, verifying that any X with bin(X)=a<r has fτ(X)<(1−ε)τ. If the inequalities survive, the theorem holds for the corrected algorithm; otherwise construct a triple (δ,ε,X) with a<r and fτ(X)≥(1−ε)τ where X∪{x*} breaches cost-effectiveness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.1 defines bin(X) using r=log_δ(ε) as both an integer bin count and the final-bin index, with final bin {fτ≥(1−ε)τ}. For arbitrary δ∈(0,1), ε∈(0,1), r is not an integer; e.g. δ=0.5, ε=0.1 gives r≈3.32. Hence 'i∈{0,...,r−1}' and 'bin(X)=r' do not define a total function, and Algorithm 1's call to bin(X') is undefined on many inputs. The proof of Part Two/Three treats r as an integer satisfying δ^r=ε: bin a+1 is assumed to exist, and the final bin is exactly the (1−ε)τ threshold. If one fixes r=ceil(log_δ ε), the top non-final interval may extend above (1−ε)τ, overlapping the final bin unless a priority rule is stated; if one uses r=floor, there are gaps. The manuscript supplies neither. This is a gap in the statement of the central claim, not merely a proof typo, because the algorithm itself is not well-defined for generic parameters. A standard repair (r=ceil, final-bin priority, and fτ(X)<(1−ε)τ for all X with bin(X)<r) appears to restore every step of the theorem, so I do not view the claim as false.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes EASC, an evolutionary algorithm for the Minimum Cost Submodular Cover (MCSC) problem. EASC maintains a population with at most one solution per benefit bin, compares solutions in the same bin by a cost-effectiveness measure φ, and mutates a uniformly random population member at each step. The main theoretical contribution is Theorem 1, which claims that, when run indefinitely with ε∈(0,1) and δ in a specific interval, EASC eventually contains a set A with f(A)≥(1−ε)τ and c(A)≤(ln(1/ε)+1)c(A*) in expected O(n^3 ((cmax/cmin) ln(1/ε))^2) iterations. The proof is organized in five parts, establishing monotonicity of a cost-effectiveness progress measure, bin progress via the greedy marginal-gain lemma, preservation of cost-effectiveness, and an expected-iteration bound. The paper also gives an experimental comparison with the greedy algorithm and the POM evolutionary algorithm on four influence-threshold instances. The exposition is generally clear, and the appendix contains proofs of the standard submodularity lemmas. However, the central algorithm and theorem are not well-defined for generic δ and ε because the bin structure uses the generally non-integer quantity log_δ(ε) as both a bin count and a final bin index; this needs a repair. A second, smaller gap appears in one subcase of the proof of Theorem 1. Both issues are fixable without changing the claimed asymptotic result.","tokens_in":12146,"tokens_out":9949,"duration_ms":94308,"significance":"If Theorem 1 holds after the necessary repairs, the paper makes a significant contribution: EASC would be the first evolutionary algorithm with an expected polynomial-time constant bicriteria approximation guarantee for MCSC, avoiding the polynomial-population assumption required by POM. The proof strategy, especially the cost-effectiveness comparison and the use of bin progress, is a genuinely useful idea that may extend to other submodular problems. The paper is also honest in noting in Proposition 2 that the same bicriteria guarantee already holds for the greedy algorithm, so the theoretical novelty is the algorithmic mechanism rather than a new approximation factor. The public code and the careful inclusion of the standard lemmas in the appendix are strengths. The experimental section is illustrative rather than decisive, since it averages only three runs and reports no variance or statistical tests.","major_comments":[{"comment":"The bin function and the algorithm are not well-defined for generic input parameters. In the definition of bin(X), the index set {0,...,log_δ(ε)−1} and the final case 'bin(X)=log_δ(ε)' require r=log_δ(ε) to be an integer, but for arbitrary δ∈(0,1) and ε∈(0,1) this is generally false; for example, δ=0.5 and ε=0.1 give r≈3.32. As a result, many subsets X are not assigned to any bin, and Algorithm 1's call to bin(X') is undefined. The proof in Section 3 also silently assumes that r is an integer and that bin a+1 exists for every a<r. The manuscript needs a repair, for instance by defining q=ceil(log_δ(ε)), indexing bins 0,...,q, giving the final bin priority whenever f(X)≥(1−ε)τ, and adjusting the population-size bound from q+1 to q+2. With such a repair, the proof steps in Parts One through Five appear to go through, but the current text does not state the repair.","section":"Section 2.1, Algorithm 1, Theorem 1"},{"comment":"The proof that {x*} is cost-effective when bin({x*})<r is incomplete in the subcase bin({x*})=0. The displayed inequality τ−fτ(x*)≤exp(−c(x*)/c(A*))τ can be rearranged to φ({x*})≤c(A*) only when φ is the ratio c/ln(τ/(τ−f)), but for bin 0 the definition in Section 2.2 sets φ({x*})=c({x*}) instead. The missing argument is supplied by Lemma 2, which gives c(x*)≤c(A*) because f(∅)<τ; invoking Lemma 2 would complete the subcase. As written, this subcase is not proved, although the repair is straightforward.","section":"Section 3, Part Three, Case (i)"}],"minor_comments":[{"comment":"The sentence 'Lower ϵ and δ values result in less bins' is backwards for ε: decreasing ε increases ln(1/ε) and hence increases the number of bins. Only decreasing δ reduces the bin count.","section":"Section 2, penultimate paragraph"},{"comment":"The experimental results average only three runs per algorithm and report no error bars, variance, or significance tests. Claims such as 'EASC converges faster than POM' in Section 4.2 should be softened or quantitatively supported.","section":"Section 4"},{"comment":"The figure labels the final bin as 'logδ(ϵ)', which is the same non-integer quantity that causes the well-definedness problem in Section 2.1; the figure should be updated to match the repaired integer bin count.","section":"Figure 1"},{"comment":"The stated expected-iteration bound of en((cmax/cmin)ln(1/ε)n + 1)^2 depends on the bin-count bound. If the repair uses q=ceil(log_δ(ε)), the additive constant becomes 2, so the bound should be restated to be consistent with the repaired definition.","section":"Theorem 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid contribution if the bin-definition issue is repaired; the proof of Theorem 1 is otherwise careful and the proposed fix is local. The experiments are under-powered but secondary. I would encourage the editor to treat the revision as substantive primarily on the well-definedness point, not on the asymptotic claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nPunchline: this is a real result—the first evolutionary algorithm for MCSC with an expected polynomial-time, constant bicriteria guarantee—and the theory holds up. But the paper has one definitional gap that must be fixed, and the experiments are too thin to carry much weight. Still, it deserves a serious referee, not a desk rejection.\n\nWhat's new: the binning scheme plus the φ cost-effectiveness measure are original, and the analysis showing a bounded population size suffices is a genuine improvement over POM, whose expected time depends on N, the number of distinct f values (possibly exponential). The author credits the prior binning ideas and the greedy analysis properly. The proof of Theorem 1 is carefully structured, and the lemmas are standard but correctly proven. The parameter δ can be set from any upper bound on c(A*) that is ≤ c(S), which is a practical workaround given c(A*) is unknown.\n\nThe main soft spot is the integer-bin issue. Section 2.1 defines the final bin as log_δ(ε), but for arbitrary δ, ε ∈ (0,1), log_δ(ε) is not an integer. As written, bin(X) is not defined for every X—there are gaps between the last non-final interval and the final threshold. This is not just a proof typo; Algorithm 1 calls bin(X') and would be undefined on some inputs. The repair is straightforward: let r be an integer (e.g., r = ceil(log_δ ε)), make the final bin [1−δ^r, 1], and adjust the proof accordingly. Every step of the proof appears to survive; the final threshold becomes stricter than (1−ε)τ, which only helps feasibility, and the expected-time bound still holds up to constants. So it's a fixable flaw, but it must be fixed before publication.\n\nThe experiments average only three runs per instance, with no error bars or significance tests. The claim of faster convergence than POM on some datasets is plausible but unproven. That's a minor-to-moderate weakness.\n\nThe reader's take is mostly right; the stress-test note about the bin index is correct and worth taking seriously.\n\nBottom line: this paper is for the evolutionary computation and submodular optimization communities. I'd bring it to my reading group and would cite it if I worked on EA guarantees, though I'd want the bin definition cleaned up first. It deserves peer review, with the referee asked to confirm the integer-bin fix and to check that the δ-satisfiability condition is stated cleanly.","headline":"Solid, first-of-its-kind EA guarantee for submodular cover; theory holds up, but the bin-index definition needs an integer repair before it's publishable.","tokens_in":12613,"tokens_out":4613,"would_cite":true,"duration_ms":42530,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An evolutionary algorithm achieves the first polynomial-time constant bicriteria guarantee for Minimum Cost Submodular Cover.","keywords":["minimum cost submodular cover","evolutionary algorithm","bicriteria approximation","expected polynomial time","submodularity","cost-effectiveness","influence threshold problem"],"falsifier":"A counterexample would be an MCSC instance with known optimum $A^*$, $\\epsilon$ constant, and $\\delta$ chosen in the permitted range $[1 - c_{\\min}/c(A^*),\\, 1 - c_{\\min}/c(S)]$, for which EASC's expected number of iterations to first place a solution in the final bin exceeds $e n ((c_{\\max}/c_{\\min}) \\ln(1/\\epsilon) n + 1)^2$ by more than a constant factor; such instances could be produced by exhaustive search over small ground sets and tested by repeated simulation.","tokens_in":11654,"feed_emoji":"🧬","tokens_out":12760,"duration_ms":112583,"temperature":0.7,"pith_summary":"This paper introduces EASC, an evolutionary algorithm for Minimum Cost Submodular Cover (MCSC), and proves that it finds a near-feasible, near-optimal solution in expected polynomial time. For any $\\epsilon \\in (0,1)$, EASC returns a set $A$ with benefit $f(A) \\ge (1-\\epsilon)\\tau$ and cost $c(A) \\le (\\ln(1/\\epsilon)+1)c(A^*)$, where $A^*$ is an optimal cover. This is the first such polynomial-time guarantee for an evolutionary algorithm on MCSC; earlier evolutionary approaches either had exponential worst-case time or required the benefit function to take only polynomially many distinct values. The algorithm partitions the benefit range into logarithmically spaced bins and keeps one cost-effective solution per bin, with a comparison rule modeled on greedy submodular cover. Experiments on influence-threshold instances show EASC improving on the greedy solution and converging faster than the existing Pareto optimization method on several networks.","feed_headline":"First evolutionary algorithm with a submodular cover guarantee","feed_subtitle":"On influence networks it finds cheaper solutions than greedy and converges faster than prior EAs.","key_machinery":"The machinery rests on a bin function that cuts $[0,\\tau]$ into $\\log_\\delta(\\epsilon)+1$ intervals of the form $[(1-\\delta^i)\\tau,(1-\\delta^{i+1})\\tau)$, with the final bin holding all sets with $f(X) \\ge (1-\\epsilon)\\tau$; each bin holds at most one solution, so the population stays at $O((c_{\\max}/c_{\\min})\\ln(1/\\epsilon)n)$. Within a bin, the comparison uses the cost-effectiveness $\\varphi(X)=c(X)/\\ln(\\tau/(\\tau-f(X)))$ (with $\\varphi(X)=c(X)$ in the first and last bins). This $\\varphi$ is chosen so that a solution with $\\varphi(X)\\le c(A^*)$ is as cost-effective as any greedy step; the bin spacing matches the greedy marginal-gain lemma, so adding the best marginal element always advances a cost-effective solution into a strictly higher bin. Two submodularity lemmas carry the argument: $\\tau - f_\\tau(X\\cup\\{x^*\\}) \\le (1 - c(x^*)/c(A^*))(\\tau - f_\\tau(X))$, and $c(x^*) \\le c(A^*)$.","core_discovery":"The central result is Theorem 1: for an MCSC instance with optimal solution $A^* \\ne \\emptyset$, if EASC is run with $\\epsilon \\in (0,1)$ and $\\delta \\in [1 - c_{\\min}/c(A^*),\\, 1 - c_{\\min}/c(S)]$, then within an expected $e n ((c_{\\max}/c_{\\min}) \\ln(1/\\epsilon) n + 1)^2$ iterations its population contains a set $A$ in the final bin with $f(A) \\ge (1-\\epsilon)\\tau$ and $c(A) \\le (\\ln(1/\\epsilon)+1)c(A^*)$. The proof shows that the highest bin containing a cost-effective set never decreases, and that a specific mutation -- adding the element with maximum marginal benefit per unit cost -- advances that bin by at least one step. When $c_{\\max}/c_{\\min}$ is polynomial in $n$ and $\\epsilon$ is constant, the expected time is polynomial, which is the first such guarantee for an evolutionary algorithm on MCSC.","pith_inferences":["If the bin-progress argument generalizes to other monotone submodular objectives (for example submodular maximization under matroid or knapsack constraints), the same logarithmic bin schedule could yield polynomial-time evolutionary guarantees for those problems, replacing generic Pareto populations.","The iteration bound scales with $(c_{\\max}/c_{\\min})^2$; for instances with exponentially skewed element costs the guarantee stops being polynomial, so the practical scope is limited to cost profiles within a polynomial factor of each other.","A tighter or looser upper bound $B$ on $c(A^*)$ changes $\\delta$ and therefore the number of bins; the theory only needs $B \\le c(S)$, so testing convergence against noisy or loose bounds (for example $B=2c(\\text{greedy})$) would probe how robust the practical runtime is to the parameter choice."],"forward_implications":["When $c_{\\max}/c_{\\min}$ is polynomially bounded in $n$ and $\\epsilon$ is constant, EASC reaches a solution meeting the guarantee in expected polynomial time; the population size stays at $O((c_{\\max}/c_{\\min})\\ln(1/\\epsilon)n)$ throughout.","Once a qualifying solution enters the final bin, the comparison rule in that bin uses only cost, so the guarantee is permanent.","Because the same $(1-\\epsilon,\\ \\ln(1/\\epsilon)+1)$ bicriteria guarantee holds for the greedy algorithm, EASC matches the worst-case guarantee while experiments show it can improve on the greedy solution.","The bin structure and cost-effectiveness comparison are designed from monotone submodularity and are presented as generalizable ideas for other submodular optimization problems."],"supporting_citations":[{"why":"Supplies the greedy algorithm's approximation analysis for MCSC, which EASC's bins and the $\\varphi$ comparator are designed to mimic.","marker":"[Wolsey, 1982]"},{"why":"Proves the same bicriteria guarantee for the greedy algorithm in the influence setting and supplies the greedy-style lemmas that EASC's proof adapts.","marker":"[Goyal et al., 2013]"},{"why":"Introduces the existing evolutionary algorithm for MCSC that EASC improves on and compares against in experiments.","marker":"[Qian et al., 2015a]"},{"why":"Source of the submodularity lemma on marginal gains (Lemma 1) used in the proof of Theorem 1.","marker":"[Nemhauser et al., 1978]"},{"why":"Establishes that expected influence spread is monotone submodular, so the tested influence-threshold instances are valid MCSC instances.","marker":"[Kempe et al., 2003]"},{"why":"Provides reverse influence sampling, the method used to approximate the benefit function in the experiments.","marker":"[Borgs et al., 2014]"}],"fun_headline_variants":["First EA with provable submodular cover","EASC: polynomial-time EA for submodular cover","Evolutionary algorithm beats greedy on submodular cover","Submodular cover: EA with constant bicriteria","New EA guarantees submodular cover in poly time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee depends on the user supplying a bin parameter $\\delta$ that is at least $1 - c_{\\min}/c(A^*)$, and since $c(A^*)$ is unknown this requires an upper bound $B$ on the optimum cost with $B \\le c(S)$, typically obtained from a greedy solution; if no such bound is available, the proof's bin-progress step fails.","fun_headline_variants_meta":{"raw":{"variants":["First EA with provable submodular cover","EASC: polynomial-time EA for submodular cover","Evolutionary algorithm beats greedy on submodular cover","Submodular cover: EA with constant bicriteria","New EA guarantees submodular cover in poly time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00036,"raw_usage":{"total_tokens":1908,"prompt_tokens":869,"completion_tokens":1039,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":963}},"tokens_in":485,"tokens_out":1039,"duration_ms":8959,"temperature":1.0,"reasoning_tokens":963,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:25:31.607193+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A counterexample would be an MCSC instance with known optimum $A^*$, $\\epsilon$ constant, and $\\delta$ chosen in the permitted range $[1 - c_{\\min}/c(A^*),\\, 1 - c_{\\min}/c(S)]$, for which EASC's expected number of iterations to first place a solution in the final bin exceeds $e n ((c_{\\max}/c_{\\min}) \\ln(1/\\epsilon) n + 1)^2$ by more than a constant factor; such instances could be produced by exhaustive search over small ground sets and tested by repeated simulation.","supporting_citations":[],"review_version":1}