{"id":"bd49277b-4ed5-4a8d-805a-40e524b958d0","arxiv_id":"2501.01071","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":1.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of submodular maximization under uniform and partition matroids, reviewing known greedy, continuous, and distributed algorithms with no new results.","lead":"This paper is a tutorial review of submodular maximization: choosing a set of items under size or group limits to maximize a diminishing-returns utility function. It covers greedy and continuous greedy algorithms, applications, and distributed variants, but contains a false inequality in its curvature derivation.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Inequality (12) is false, and the paper's proof of the curvature-dependent greedy bound alpha_uniform=(1/c)(1-e^{-c}) depends on it; the survey needs a corrected derivation or an explicit citation to the original proof.","rationale":"The paper is a survey with no new theorems, so its value is exactly as a reliable synthesis. The reader's weakest assumption targets inequality (12), and my independent check confirms it: the sqrt(|S|) example is a valid normal monotone submodular function, c ~ 0.682, and (12) fails. The same inequality is used in Section 4 as the sole bridge from the standard greedy argument to the curvature-dependent uniform bound. Thus the defect is not merely cosmetic; it invalidates the displayed proof. However, the end result alpha_uniform=(1/c)(1-e^{-c}) is a correct theorem from [31], and the paper also cites [31] for the partition-matroid curvature bound without relying on (12). So the right disposition is CONDITIONAL, not REJECT: correct the proof or citation, and the survey can serve its stated purpose. I agree with the reader's identification of this as the weakest assumption.","tokens_in":19675,"tokens_out":12604,"duration_ms":117381,"concrete_test":"Run the counterexample: for f(S)=sqrt(|S|), P={1,2,3}, R={1,2}, S={2}, compute c from (10) and evaluate both sides of (12). If the inequality fails (as it does: LHS 0, RHS ~ 0.036), then the derivation in Section 4 is invalid. Then consult the original proof in [31] to confirm that the correct alpha_uniform bound is nevertheless true; if so, the fix is to replace the derivation with a faithful proof or a direct citation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central expository claim—that the survey can serve as a reliable foundation—is undermined by the assertion, in the derivation of the uniform-matroid curvature bound in Section 4, that for every normal monotone submodular f and all R,S, f(R union S)-f(R) >= f(S)-c f(R). This is not a harmless strengthening. Take f(S)=sqrt(|S|) on ground set {1,2,3}, which is normal, monotone, and submodular. Its total curvature is c = 1 - min_{R,p}(sqrt(|R|+1)-sqrt(|R|)) = 1 - (sqrt(3)-sqrt(2)) ~ 0.682. With R={1,2} and S={2}, the left side is f({1,2})-f({1,2}) = 0, while the right side is sqrt(1) - c*sqrt(2) ~ 0.036. So (12) is false. The displayed proof immediately uses (12) to obtain f(S*)-c f(S_i) <= kappa(f(S_{i+1})-f(S_i)), and this is exactly the step that produces the claimed alpha_uniform. The theorem itself is a known correct result of Conforti and Cornuejols [31], so the survey can be repaired by replacing the invalid derivation with a correct one or by citing the original proof explicitly; but as written, a false inequality in a reference work is a load-bearing correctness defect.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript is a survey/tutorial on submodular maximization subject to uniform and partition matroid constraints. It covers the definitions of submodularity, matroids, curvature, the multilinear extension, the sequential greedy algorithm and its approximation guarantees, the continuous greedy algorithm, several applications (exemplar-based clustering, data harvesting, optimal welfare, sensor placement, persistent monitoring), and distributed formulations. The paper presents no new theorems; its value is meant to lie in accurate synthesis and in providing a reliable foundation for researchers entering the area.","tokens_in":20022,"tokens_out":9698,"duration_ms":81884,"significance":"If accurate, the survey would be a useful entry point, especially for the systems and control community, because it collects standard results, applications, and references in one place and includes an instructive overview of distributed algorithms. The paper is generally well organized and appropriately attributes results to original sources rather than claiming novelty. However, because the stated aim is to be a solid foundation, correctness of the derivations is load-bearing; the false inequality in Section 2 (Eq. (12)) undermines the self-contained proof of the curvature-dependent greedy bound in Section 4. The error is local and repairable, but as written the survey cannot serve as a dependable reference.","major_comments":[{"comment":"The inequality f(R∪S) − f(R) ≥ f(S) − c f(R) is stated for all normal monotone submodular functions, but it is false. A counterexample is f(S) = sqrt(|S|) on ground set {1,2,3}, which is normal, monotone, and submodular. With R={1,2} and S={2}, the total curvature is c = 1 − (sqrt(3) − sqrt(2)) ≈ 0.682, and the claimed inequality reads 0 ≥ 1 − 0.682·sqrt(2) ≈ 0.036, a contradiction. This is not a harmless strengthening: it is used directly in Section 4 to derive the curvature bound for the uniform matroid.","section":"Section 2, Eq. (12)"},{"comment":"The displayed derivation of α_uniform = (1/c)(1 − e^{−c}) is invalid as written because it explicitly invokes the false inequality (12) to obtain f(S⋆∪S_i) − f(S_i) ≥ f(S⋆) − c f(S_i), and the subsequent algebra leading to δ_{i+1} ≤ (1 − c/κ) δ_i depends on that step. The theorem itself is correct (Conforti and Cornuejols [31]), so the survey must either replace the derivation with a correct one or explicitly cite the original proof; a false argument for a central result is not acceptable in a reference work.","section":"Section 4, curvature-bound derivation"}],"minor_comments":[{"comment":"The word \"submodular\" in Definition 4 should be \"modular\"; Eq. (6) defines modularity, as the following sentence indicates.","section":"Definition 4"},{"comment":"The quantifier \"∀S,R∈P\" should read \"∀S,R⊆P\" because S and R are subsets of the ground set, not elements.","section":"Definition 3"},{"comment":"The notation contains several typos: \"p<R\", \"p<S)\", and \"min_{S⊂P,p<S)}\" should be written with \"p∉R\" or \"p∉S\" as appropriate.","section":"Section 2, curvature derivation"},{"comment":"The sentence \"hard to approximate this problem within a factor better than 1−1/e≈ 0.63%\" has the percentage sign in the wrong place; it should be ≈ 0.63, not 0.63%.","section":"Section 4, hardness statement"},{"comment":"The case c = 0 is not addressed for the uniform-matroid bound; α_uniform = (1/c)(1 − e^{−c}) is undefined at c = 0 and should be interpreted via the limit, which equals 1.","section":"Section 4, curvature-bound proof"},{"comment":"In the definition of the partition matroid, the text should refer to κ_i rather than κ, and the notation \"P∪N i=1Pi\" is garbled; it should read P = ∪_{i=1}^N P_i.","section":"Introduction, Eq. (4)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a survey with no new technical results, and Section 5 draws substantially on the author's own prior work; the citations are present, but the editor should assess whether the journal welcomes survey contributions of this kind. The false inequality in Section 2 is a repairable error, but it prevents publication in the current form because the stated goal of being a reliable foundation is undermined."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a competent survey, not a research contribution, and its main value is exposing the controls/systems community to submodular maximization. The standard results are stated correctly, the applications section is grounded, and the distributed section draws sensibly on the author's own prior work. But the proof of the curvature-dependent greedy bound in Section 4 is wrong: inequality (12) is false, and the displayed derivation uses it. The theorem itself is correct, so this is a repair, not a rejection.\n\nWhat's new: nothing. It's an exposition. What's good: the presentation is clear, the examples (clustering, sensor placement, persistent monitoring) are well chosen, and the citations to the classics (Nemhauser, Conforti-Cornuejols, Vondrák) are proper. Section 5 gives a fair overview of distributed algorithms, including the message-passing and consensus variants, and it does not oversell the author's own contributions.\n\nThe soft spot: Section 4, around equations (11)-(12). The paper claims that for any normal monotone submodular f and any sets R,S, f(R∪S)-f(R) ≥ f(S)-c f(R). That is not true. The counterexample in the referee note—f(S)=√|S| on a three-element ground set with R={1,2}, S={2}—is correct and kills the displayed proof of α_uniform = (1/c)(1-e^{-c}). Since that proof is the one place where the survey goes beyond quoting known results, the error is load-bearing for the exposition, though not for the mathematics itself. The bound is correct; it's in Conforti-Cornuejols (1984). The fix is straightforward: either give a correct derivation or explicitly cite the original proof and say the derivation is omitted.\n\nMinor issues: a few typos and notational slips (e.g., \"ar\" typo, \"STOC\" venue typos), and the claim that the (1-1/e) bound is tight for all matroids is stated without the necessary caveat about the value oracle model. These are minor.\n\nWho is this for? Graduate students in control and robotics who want a first map of submodular maximization. For that audience it is genuinely useful if the proof defect is patched. As a serious referee, I would send it to review—the survey fills a real pedagogical gap—but I would require the false inequality to be removed or corrected before publication.\n\nRecommendation: engage with it, but don't cite the curvature derivation until it's fixed.","headline":"A useful survey for the controls audience, but the curvature-bound derivation rests on a false inequality; easily fixed by citing Conforti-Cornuejols.","tokens_in":20476,"tokens_out":1879,"would_cite":false,"duration_ms":17118,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","05B35","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This survey argues that monotone submodular maximization under uniform and partition matroids is a practical design tool: sequential greedy gives certified 1−1/e and 1/2 gaps, continuous greedy reaches 1−1/e for partition matroids, and…","keywords":["submodular maximization","uniform matroid","partition matroid","sequential greedy algorithm","continuous greedy algorithm","multilinear extension","distributed optimization","total curvature"],"falsifier":"Evaluate $f(S)=\\sqrt{|S|}$ on ground set $\\{1,2,3\\}$ with $R=\\{1,2\\}$ and $S=\\{2\\}$: the left-hand side of inequality (12) is $0$, since $\\sqrt{2}-\\sqrt{2}=0$, while the right-hand side is $1 - c\\sqrt{2} > 0$ for $c = 1 - (\\sqrt{3}-\\sqrt{2}) \\approx 0.682$, so the inequality fails and the survey's proof chain needs a different step.","tokens_in":19491,"feed_emoji":"📈","tokens_out":11444,"duration_ms":98872,"temperature":0.7,"pith_summary":"This paper is a survey that assembles the theory of maximizing monotone submodular set functions, functions whose marginal gains diminish as the selected set grows, under two common constraints: choosing at most κ elements overall (uniform matroid) and choosing at most κ_i elements from each of several groups (partition matroid). It argues that these abstract problems are a practical backbone for resource allocation, and that two algorithm families solve them with known performance guarantees: the sequential greedy algorithm gives at least 1−1/e of optimal for the uniform case and 1/2 for the partition case, while the continuous greedy method with rounding reaches 1−1/e for partition matroids. The paper also lays out how these algorithms can be run when data or decision sets are distributed among agents, and what the distributed guarantees look like. A sympathetic reader would take the paper's contribution to be a clear map of this territory, definitions, canonical proofs, applications, and known bounds, that researchers can use to recognize submodular problems and pick an algorithm with a certified gap.","feed_headline":"Greedy guarantees 63% for uniform, 50% for partition matroids","feed_subtitle":"These certified ratios make submodular set-choice practical for resource allocation and distributed systems.","key_machinery":"The paper's machinery is the monotone submodular set function, whose defining property is diminishing returns: adding an element to a smaller set gives at least as much gain as adding it to a larger set, together with total curvature c, uniform and partition matroids as feasibility constraints, and two algorithmic engines: the sequential greedy iteration and the multilinear extension F(x) = E[f(R_x)] over the matroid polytope, driven by the continuous greedy flow and finished by pipage rounding. The greedy update carries the 1−1/e and 1/2 arguments; the multilinear extension carries the 1−1/e argument for partition matroids; curvature c enters through the paper's inequality (12) to sharpen both bounds.","core_discovery":"On its own terms, this paper claims that the theory of submodular maximization under uniform and partition matroids is mature enough to serve as a practical design tool. For a monotone submodular utility, the sequential greedy algorithm returns a set of size κ whose value is at least (1−1/e)OPT, and at least OPT/2 when exactly κ_i elements may be taken from each partition block; if the total curvature c is known, the survey derives the sharper gaps (1/c)(1−$e^{{−c}}$) and 1/(1+c). It further claims that the continuous greedy method on the multilinear extension, followed by pipage rounding, recovers the 1−1/e guarantee for partition matroids, and that these algorithms can be decentralized: sequential message-passing preserves OPT/2 when all agents are reached, with a guarantee that degrades to f ≥ OPT/(2+n−W) when the information graph is incomplete, while consensus-based versions of continuous greedy are feasible in special cases (each agent picks one option, c=1). The paper positions this collection of definitions, proof sketches, and applications, sensor placement, traffic flow identification, persistent monitoring, data harvesting, welfare maximization, as the bridge between the theory literature and engineering practice. The curvature refinement in the paper's exposition is argued through the asserted inequality f(R∪S)−f(R) ≥ f(S)−c f(R).","pith_inferences":["The curvature-sharpened guarantees (1/c)(1−e^{−c}) and 1/(1+c) are known-correct results in the literature, but the survey's own derivation of the uniform case leans on inequality (12); because that inequality is not generally true, the survey as a self-contained source needs a different proof at that step.","The analysis tying the optimality gap to the clique number of the information graph suggests a design principle that the paper leaves implicit: in networked missions, spending communication budget on graph connectivity directly purchases a better worst-case approximation guarantee.","The distributed continuous-greedy results in the paper are limited to κ_i=1 and c=1; a natural testable extension is to combine sampled gradient estimates with consensus algorithms for larger strategy budgets, which the survey flags as scarce."],"forward_implications":["For a monotone submodular function and a cardinality cap κ, running the sequential greedy rule yields a set whose value is at least (1−1/e)OPT, so practitioners can rely on this simple algorithm on large ground sets where exact solving is NP-hard.","For a partition matroid, the same greedy rule guarantees OPT/2, and since no constant factor better than 1−1/e is possible in general, the continuous greedy route is the way to reach the 1−1/e barrier.","When the total curvature c is known, the bounds tighten to (1/c)(1−e^{−c}) for uniform and 1/(1+c) for partition; assuming c=1 is the conservative choice when curvature is unknown.","In distributed settings with a connected information graph that has a Hamiltonian path over the agents, sequential message-passing achieves the centralized 1/2 guarantee; with incomplete communication the guarantee decays to 1/(2+n−W) where W is the clique number of the information graph.","The multilinear-extension and continuous-greedy approach, after pipage rounding, converts the fractional 1−1/e solution into an integral feasible set without loss, establishing the tightest known worst-case guarantee for partition matroids."],"supporting_citations":[{"why":"Establishes the (1−1/e) optimality gap for the sequential greedy algorithm under a cardinality constraint; the survey reproduces this proof.","marker":"[29]"},{"why":"Source of the curvature-refined gaps (1/c)(1−e^{−c}) and 1/(1+c) for uniform and partition matroids.","marker":"[31]"},{"why":"Introduces the multilinear extension and continuous greedy algorithm that achieve the 1−1/e bound for the submodular welfare problem.","marker":"[20]"},{"why":"Supplies the rigorous continuous-greedy analysis for maximization under a matroid constraint, used for the partition-matroid result.","marker":"[33]"},{"why":"Pipage rounding method that converts the fractional continuous-greedy solution into an integral feasible set without loss.","marker":"[35]"},{"why":"Formulates multi-agent persistent monitoring as partition-matroid submodular maximization; serves as the survey's motivating application and distributed example.","marker":"[17]"},{"why":"Gives the distributed optimality-gap bound for incomplete message-passing information graphs, f(SSG) ≥ f(S*)/(2+n−W(G_I)).","marker":"[52]"},{"why":"Proposes the max-consensus distributed continuous-greedy variant with stochastic rounding, the paper's main distributed continuous method.","marker":"[51]"}],"fun_headline_variants":["Greedy hits 63% uniform, 50% partition; curvature sharpens both","Distributed greedy preserves half-optimality under complete message passing","Curvature-aware bounds tighten greedy guarantees for matroids","Matroid-constrained submodular selection: greedy and distributed, with curvature"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The derivation of the curvature-sharpened uniform-matroid gap depends on the asserted inequality $f(R \\cup S) - f(R) \\ge f(S) - c\\, f(R)$ being true for every normal monotone submodular function, and that inequality is not generally true.","fun_headline_variants_meta":{"raw":{"variants":["Greedy hits 63% uniform, 50% partition; curvature sharpens both","Distributed greedy preserves half-optimality under complete message passing","Curvature-aware bounds tighten greedy guarantees for matroids","Matroid-constrained submodular selection: greedy and distributed, with curvature"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00102,"raw_usage":{"total_tokens":4325,"prompt_tokens":988,"completion_tokens":3337,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":3258}},"tokens_in":604,"tokens_out":3337,"duration_ms":23908,"temperature":1.0,"reasoning_tokens":3258,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:38:16.742571+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate $f(S)=\\sqrt{|S|}$ on ground set $\\{1,2,3\\}$ with $R=\\{1,2\\}$ and $S=\\{2\\}$: the left-hand side of inequality (12) is $0$, since $\\sqrt{2}-\\sqrt{2}=0$, while the right-hand side is $1 - c\\sqrt{2} > 0$ for $c = 1 - (\\sqrt{3}-\\sqrt{2}) \\approx 0.682$, so the inequality fails and the survey's proof chain needs a different step.","supporting_citations":[{"cited_title":"An analysis of approximations for maximizing sub- modular set functions—i,","cited_arxiv_id":null,"evidence_quote":"Establishes the (1−1/e) optimality gap for the sequential greedy algorithm under a cardinality constraint; the survey reproduces this proof."},{"cited_title":"Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem,","cited_arxiv_id":null,"evidence_quote":"Source of the curvature-refined gaps (1/c)(1−e^{−c}) and 1/(1+c) for uniform and partition matroids."},{"cited_title":"Optimal approximation for the submodular welfare problem in the value oracle model,","cited_arxiv_id":null,"evidence_quote":"Introduces the multilinear extension and continuous greedy algorithm that achieve the 1−1/e bound for the submodular welfare problem."},{"cited_title":"Maximizing a monotone submodular func- tion subject to a matroid constraint,","cited_arxiv_id":null,"evidence_quote":"Supplies the rigorous continuous-greedy analysis for maximization under a matroid constraint, used for the partition-matroid result."},{"cited_title":"Pipage rounding: A new method of constructing algorithms with proven performance guarantee,","cited_arxiv_id":null,"evidence_quote":"Pipage rounding method that converts the fractional continuous-greedy solution into an integral feasible set without loss."},{"cited_title":"Distributed submodular maximization with limited information,","cited_arxiv_id":null,"evidence_quote":"Gives the distributed optimality-gap bound for incomplete message-passing information graphs, f(SSG) ≥ f(S*)/(2+n−W(G_I))."},{"cited_title":"Distributed strategy selection: A submodular set function maxi- mization approach,","cited_arxiv_id":null,"evidence_quote":"Proposes the max-consensus distributed continuous-greedy variant with stochastic rounding, the paper's main distributed continuous method."}],"review_version":1}