Pith. sign in

REVIEW 2 major objections 6 minor 2 cited by

Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions

T0 review · 2 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict A useful survey for the controls audience, but the curvature-bound derivation rests on a false inequality; easily fixed by citing Conforti-Cornuejols. read the letter →

arxiv 2501.01071 v1 pith:6OIBQ5HO submitted 2025-01-02 cs.DS

Solmaz S. Kia This is my paper · ORCID
classification cs.DS MSC 90C2705B3568W25
keywords submodularmaximizationuniformmatroidpartitionsequentialgreedyalgorithmcontinuousmultilinearextensiondistributedoptimizationtotalcurvature
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [Section 2, Eq. (12)] 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.
  2. [Section 4, curvature-bound derivation] 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.
minor comments (6)
  1. [Definition 4] The word "submodular" in Definition 4 should be "modular"; Eq. (6) defines modularity, as the following sentence indicates.
  2. [Definition 3] The quantifier "∀S,R∈P" should read "∀S,R⊆P" because S and R are subsets of the ground set, not elements.
  3. [Section 2, curvature derivation] 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.
  4. [Section 4, hardness statement] 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%.
  5. [Section 4, curvature-bound proof] 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.
  6. [Introduction, Eq. (4)] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the survey's claims are externally attributed; the identified defect (false inequality (12)) is a correctness error, not a circularity.

full rationale

This is a survey with no new theorems, so the usual circularity failure modes—fitted inputs called predictions, definitions that presuppose their targets, or uniqueness imported from the authors' own prior proof—are absent. Section 4 reproduces the classical greedy proof of the (1-1/e) bound and explicitly attributes the curvature refinement to Conforti and Cornuejols [31]; the curvature-dependent derivation is presented as a proof sketch, but inequality (12) is not obtained by renaming an input or by assuming the conclusion. The self-citations in Section 5 ([17], [51], [53], [64]) point to prior peer-reviewed publications and are used as literature pointers, not as premises that force the survey's conclusions, so no circular step can be quoted. The one serious defect is mathematical rather than circular: inequality (12) is false, as shown by f(S)=sqrt(|S|) with R={1,2}, S={2}; the displayed proof of alpha_uniform=(1/c)(1-e^{-c}) relies on it. Because the final bound is correctly attributed to Conforti and Cornuejols, the survey can be repaired by replacing the invalid proof sketch with a correct citation or derivation. This correctness risk does not raise the circularity score beyond a token acknowledgment of the present author's self-citations.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or new entities are introduced. The survey's content rests on standard submodularity theory and on the correctness of cited theorems. One asserted inequality is false, which we record as an ad hoc assumption because the paper treats it as given.

assumptions (4)
  • standard math Submodular functions satisfy the diminishing returns property (Definition 3, Eq. (8))
    Used as the basis for greedy optimality proofs throughout Section 4.
  • standard math The multilinear extension F(x) equals the expected value of f over a random set with independent elements (Section 2, Eq. (14))
    Central to the continuous greedy discussion in Section 4.
  • domain assumption The classic optimality gaps for greedy and continuous greedy are correct as cited (Nemhauser et al., Conforti-Cornuejols, Vondrák)
    The paper reproduces these theorems as factual background and does not re-prove them.
  • ad hoc to paper Inequality (12) f(R∪S)−f(R) ≥ f(S)−c f(R) holds for all normal monotone submodular functions
    This is asserted in Section 2 and used in the curvature derivation, but it is false; a counterexample is f(S)=sqrt(|S|) with R={1,2}, S={2}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions." pith.science (2026). https://pith.science/paper/6OIBQ5HO

@misc{pith2026250101071,
  author       = {Pith},
  title        = {Pith review of: Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6OIBQ5HO}},
  note         = {Machine review of arXiv:2501.01071}
}
read the original abstract

This article provides a comprehensive exploration of submodular maximization problems, focusing on those subject to uniform and partition matroids. Crucial for a wide array of applications in fields ranging from computer science to systems engineering, submodular maximization entails selecting elements from a discrete set to optimize a submodular utility function under certain constraints. We explore the foundational aspects of submodular functions and matroids, outlining their core properties and illustrating their application through various optimization scenarios. Central to our exposition is the discussion on algorithmic strategies, particularly the sequential greedy algorithm and its efficacy under matroid constraints. Additionally, we extend our analysis to distributed submodular maximization, highlighting the challenges and solutions for large-scale, distributed optimization problems. This work aims to succinctly bridge the gap between theoretical insights and practical applications in submodular maximization, providing a solid foundation for researchers navigating this intricate domain.

Figures

Figures reproduced from arXiv: 2501.01071 by the authors.

Figure 1
Figure 1. Properties of submodular functions. This article will focus on solution approaches, application examples and distributed implementa￾tion of the two most well-know submodular maximization problems that are selecting elements from a finite discrete ground set P to maximize a submodular utility function, namely • Submodular maximization subject to uniform matroid constraint S ⋆ = arg max S⊂P f(S) subject to |S| ≤ κ, (3… view at source ↗
Figure 2
Figure 2. Multilinear extension extends a submodular function f(R) to the continuous space defined on hyper￾cube [0, 1]n . F(x) agrees with f(R) on the vertices of the hypercube (for integral x). greatest reduction in marginal gains for adding elements to a set. Specifically, it signifies that there is at least one situation where adding an element to a larger set grants no additional value compared to adding it to some small… view at source ↗
Figure 3
Figure 3. A simple schematic illustration of a distributed sensor deployment for data harvesting involving a group of agents A. Each agent i ∈ A possesses κi data harvesting drones, which can be deployed at a set of pre-assigned deployment points Bi , indicated by the same color used to depict the agent. The agents communicate over a connected graph to determine the optimal deployment positions for the team, as defined by the… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The top figures illustrate the communication topology (solid black arrows) and the message-passing sequence (dashed red arrows). The bottom figures detail the information-sharing graph. In case (a), the com￾munication graph possesses a Hamiltonian path, enabling the sh…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization

    cs.DM 2025-05 conditional novelty 5.0 of 10

    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.

  2. NavEX: A Multi-Agent Coverage in Non-Convex and Uneven Environments via Exemplar-Clustering

    cs.MA 2025-04 reject novelty 4.0 of 10

    NavEX casts multi-agent deployment in non-convex or uneven terrain as submodular maximization over exemplar clustering with visibility-graph or RRT* distance metrics.

Reference graph

Works this paper leans on

71 extracted references · 66 canonical work pages · cited by 2 Pith papers

  1. [31]

    Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem,

    M. Conforti and G. Cornu ´ejols, “Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem,” Discrete applied mathematics, vol. 7, no. 3, pp. 251–274, 1984

    work page 1984

  2. [1]

    Providing Meaningful Data Summarizations Using Exemplar-based Clustering in Industry 4.0

    P. Honysz, A. Schulze-Struchtrup, S. Buschj ¨ager, and K. Morik, “Providing meaningful data summarizations using exemplar-based clustering in industry 4.0.” https://arxiv.org/abs/ 2105.12026, 2021

    work page Pith review arXiv 2021

  3. [2]

    Categorical feature compression via submodular optimization,

    A. Rostamizadeh, H. Esfandiari, L. Chen, MohammadHossein, Bateni, T. Fu, and V . Mirrokni, “Categorical feature compression via submodular optimization,” inInternational Conference on Machine Learning, (Long Beach, California), pp. 515–523, 2019

    work page 2019

  4. [3]

    Beyond keyword search: discovering relevant scientific literature,

    K. El-Arini and C. Guestrin, “Beyond keyword search: discovering relevant scientific literature,” in International Conference on Knowledge Discovery and Data Mining, (San Diego, California), pp. 439–447, 2011

    work page 2011

  5. [4]

    Max-sum diversification, monotone submodular functions, and dynamic updates,

    A. Borodin, A. Jain, H. C. Leel, and Y . Ye, “Max-sum diversification, monotone submodular functions, and dynamic updates,” ACM Transactions on Algorithms , vol. 13, no. 3, pp. 1–25, 2017

    work page 2017

  6. [5]

    Max-sum diversification, monotone submodular functions and dynamic updates,

    K. Wei, R. Iyer, and J. Bilmes, “Max-sum diversification, monotone submodular functions and dynamic updates,” in International Conference on Machine Learning, vol. 37, pp. 1954–1963, 2015

    work page 1954

  7. [6]

    Community-based rumor blocking maximization in social networks: Algorithms and analysis,

    Q. Ni, J. Guo, C. Huang, and W. Wu, “Community-based rumor blocking maximization in social networks: Algorithms and analysis,” Theoretical Computer Science, vol. 840, pp. 257– 269, 2020

    work page 2020

  8. [7]

    Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies,

    A. Krause, A. Singh, and C. Guestrin, “Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies,” Journal of Machine Learning Research , vol. 9, no. Feb, pp. 235–284, 2008

    work page 2008

Show all 71 references
  1. [8]

    On submodularity and controllability in complex dy- namical networks.,

    T. Summers, F. Cortesi, and J. Lygeros, “On submodularity and controllability in complex dy- namical networks.,”IEEE Transactions on Control of Network Systems, vol. 3, no. 1, pp. 91–101, 2016

    2016

  2. [9]

    Submodular optimiza- tion for voltage control,

    Z. Liu, A. Clark, P. Lee, L. Bushnell, D. Kirschen, and R. Poovendran, “Submodular optimiza- tion for voltage control,” IEEE Tranactions on Power Systems , vol. 33, no. 1, pp. 502–513, 2018

    2018

  3. [10]

    Combinatorial algorithms for control of biological regulatory networks,

    A. Clark, P. Lee, B. Alomair, L. Bushnell, and R. Poovendran, “Combinatorial algorithms for control of biological regulatory networks,” IEEE Transactions on Control of Network Systems, vol. 5, no. 2, pp. 748–759, 2018

    2018

  4. [11]

    Near-optimal observation selection using submodular functions,

    A. Krause and C. Guestrin, “Near-optimal observation selection using submodular functions,” in American Association for Artificial Intelligence, vol. 7, pp. 1650–1654, 2007

    2007

  5. [12]

    A supermodular optimization framework for leader selection under link noise in linear multi-agent systems,

    A. Clark, L. Bushnell, and R. Poovendran, “A supermodular optimization framework for leader selection under link noise in linear multi-agent systems,”IEEE Transactions on Automatic Con- trol, vol. 59, no. 2, pp. 283–296, 2014. 18 REFERENCES REFERENCES

    2014

  6. [13]

    Submodularity of storage placement optimization in power networks,

    J. Qin, I. Yang, and R. Rajagopal, “Submodularity of storage placement optimization in power networks,” IEEE Transactions on Automatic Control, vol. 64, no. 8, pp. 3268–3283, 2019

    2019

  7. [14]

    On the greedy placement of energy storage systems in distribution grids,

    M. Bucciarelli, S. Paoletti, E. Dall’Anese, and A. Vicino, “On the greedy placement of energy storage systems in distribution grids,” in American Control Conference, 2020

    2020

  8. [15]

    Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems,

    S. T. Jawaid and S. Smith, “Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems,” Automatica, vol. 61, pp. 282–288, 2015

    2015

  9. [16]

    Towards scalable volt- age control in smart grid: A submodular optimization approach,

    Z. Liu, A. Clark, P. Lee, L. Bushnell, D. Kirschen, and R. Poovendran, “Towards scalable volt- age control in smart grid: A submodular optimization approach,” in ACM/IEEE International Conference on Cyber-Physical Systems, (Vienna, Austria), 2016

    2016

  10. [17]

    A sub-modular receding horizon solution for mobile multi-agent persistent monitoring,

    N. Rezazadeh and S. S. Kia, “A sub-modular receding horizon solution for mobile multi-agent persistent monitoring,” Automatica, vol. 127, p. 109460, 2021

    2021

  11. [18]

    C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity . Courier Corporation, 1998

    1998

  12. [19]

    Fujishige, Submodular functions and optimization

    S. Fujishige, Submodular functions and optimization. Elsevier, 2005

    2005

  13. [20]

    Optimal approximation for the submodular welfare problem in the value oracle model,

    J. V ondr´ak, “Optimal approximation for the submodular welfare problem in the value oracle model,” inACM Symposium on Theory of Computing, (Victoria (BC), Canada), pp. 67–74, 2008

    2008

  14. [21]

    Continuous dr-submodular maximization: Structure and algorithms,

    A. Bian, K. Levy, A. Krause, and J. M. Buhmann, “Continuous dr-submodular maximization: Structure and algorithms,” Advances in Neural Information Processing Systems, vol. 30, 2017

    2017

  15. [22]

    A unified approach for maximizing continuous dr-submodular functions,

    M. Pedramfar, C. Quinn, and V . Aggarwal, “A unified approach for maximizing continuous dr-submodular functions,” Advances in Neural Information Processing Systems, vol. 36, 2024

    2024

  16. [23]

    Submodular function maximization,

    A. Krause and D. Golovin, “Submodular function maximization,” in Tractability: Practical Approaches to Hard Problems (L. Bordeaux, Y . Hamadi, and P. Kohli, eds.), pp. 71–104, Cam- bridge, UK: Cambridge University Press, 2014

    2014

  17. [24]

    Kaufman and P

    L. Kaufman and P. J. Rousseeuw, Finding groups in data: an introduction to cluster analysis . John Wiley & Sons, 2009

    2009

  18. [25]

    Budgeted nonparametric learning from data streams,

    R. Gomes and A. Krause, “Budgeted nonparametric learning from data streams,” in Interna- tional Conference on Machine Learning, vol. 1, (Haifa, Israel), p. 3, 2010

    2010

  19. [26]

    Combinatorial auctions with decreasing marginal utilities,

    D. J. L. B. Lehmann and N. Nisan, “Combinatorial auctions with decreasing marginal utilities,” Games and Economic Behavior, vol. 55, pp. 270–296, 2006

    2006

  20. [27]

    A submodular approach for optimal sensor placement in tra ffic networks,

    N. Mehr and R. Horowitz, “A submodular approach for optimal sensor placement in tra ffic networks,” in American Control Conference, (Milwaukee, Wisconsin), pp. 6353–6358, 2018

    2018

  21. [28]

    An analysis of approximations for maximizing sub- modular set functions—ii,

    L. Fisher, G. Nemhauser, and L. Wolsey, “An analysis of approximations for maximizing sub- modular set functions—ii,” in Polyhedral Combinatorics, pp. 73–87, Springer, 1978

    1978

  22. [29]

    An analysis of approximations for maximizing sub- modular set functions—i,

    G. Nemhauser, L. Wolsey, and M. Fisher, “An analysis of approximations for maximizing sub- modular set functions—i,” Mathematical Programming, vol. 14, no. 1, pp. 265–294, 1978

    1978

  23. [30]

    Best algorithms for approximating the maximum of a submodular set function,

    G. L. Nemhauser and L. A. Wolsey, “Best algorithms for approximating the maximum of a submodular set function,” Math. Operations Research, vol. 3, no. 3, pp. 177–188, 1978. 19 REFERENCES REFERENCES

    1978

  24. [32]

    A threshold of ln n for approximating set cover,

    U. Feige, “A threshold of ln n for approximating set cover,” Journal of the ACM, vol. 45, no. 4, pp. 634–652, 1998

    1998

  25. [33]

    Maximizing a monotone submodular func- tion subject to a matroid constraint,

    G. Calinescu, C. Chekuri, M. Pal, and J. V ondrak, “Maximizing a monotone submodular func- tion subject to a matroid constraint,”SIAM Journal on Computing, vol. 40, no. 6, pp. 1740–1766, 2011

    2011

  26. [34]

    An algorithm for quadratic programming,

    M. Frank, P. Wolfe, et al., “An algorithm for quadratic programming,” Naval research logistics quarterly, vol. 3, no. 1-2, pp. 95–110, 1956

    1956

  27. [35]

    Pipage rounding: A new method of constructing algorithms with proven performance guarantee,

    A. Ageev and M. Sviridenko, “Pipage rounding: A new method of constructing algorithms with proven performance guarantee,” Journal of Combinatorial Optimization, vol. 8, no. 3, pp. 307– 328, 2004

    2004

  28. [36]

    Probability inequalities for sums of bounded random variables,

    H. W, “Probability inequalities for sums of bounded random variables,” in The Collected Works of Wassily Hoeffding, pp. 409–426, Springer, 1994

    1994

  29. [37]

    Submodularity and curvature: The optimal algorithm,

    J. V ondr´ak, “Submodularity and curvature: The optimal algorithm,” RIMS Kˆ okyˆ uroku Bessatsu, vol. 23, pp. 253–266, 2010

    2010

  30. [38]

    Submodular function maximization via the multilin- ear relaxation and contention resolution schemes,

    C. Chekuri, J. V ondrak, and R. Zenklusen, “Submodular function maximization via the multilin- ear relaxation and contention resolution schemes,” SIAM Journal on Computing, vol. 43, no. 6, pp. 1831–1879, 2014

    2014

  31. [39]

    Guaranteed non-convex optimiza- tion: Submodular maximization over continuous domains,

    A. A. Bian, B. Mirzasoleiman, J. Buhmann, and A. Krause, “Guaranteed non-convex optimiza- tion: Submodular maximization over continuous domains,” in Artificial Intelligence and Statis- tics, pp. 111–120, 2017

    2017

  32. [40]

    Stochastic conditional gradient methods: From convex minimization to submodular maximization,

    A. Mokhtari, H. Hassani, and A. Karbasi, “Stochastic conditional gradient methods: From convex minimization to submodular maximization,” Journal of Machine Learning Research , vol. 21, no. 105, pp. 1–49, 2020

    2020

  33. [41]

    Online continuous DR-submodular maximization with long- term budget constraints,

    O. Sadeghi and M. Fazel, “Online continuous DR-submodular maximization with long- term budget constraints,” in International Conference on Artificial Intelligence and Statistics , pp. 4410–4419, 2020

    2020

  34. [42]

    Fast multi-stage submodular maximization,

    K. Wei, R. Iyer, and J. Bilmes, “Fast multi-stage submodular maximization,” in International conference on machine learning, pp. 1494–1502, PMLR, 2014

    2014

  35. [43]

    Distributed submodular maximiza- tion: Identifying representative elements in massive data,

    B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, “Distributed submodular maximiza- tion: Identifying representative elements in massive data,” in Advances in Neural Information Processing Systems, pp. 2049–2057, 2013

    2013

  36. [44]

    The power of randomization: distributed sub- modular maximization on massive datasets,

    R. Barbosa, A. Ene, H. L. Nguyen, and J. Ward, “The power of randomization: distributed sub- modular maximization on massive datasets,” inInternational Conference on Machine Learning, vol. 37, (Lille, France), pp. 1236–1244, 2015

    2015

  37. [45]

    Distributed submodular maximiza- tion,

    B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, “Distributed submodular maximiza- tion,” Journal of Machine Learning Research, vol. 17, pp. 1–44, 2016. 20 REFERENCES REFERENCES

    2016

  38. [46]

    Fast distributed submodular cover: Public-private data summarization,

    B. Mirzasoleiman, M. Zadimoghaddam, and A. Karbasi, “Fast distributed submodular cover: Public-private data summarization,” in Advances in Neural Information Processing Systems , pp. 3594–3602, 2016

    2016

  39. [47]

    Fast greedy algorithms in mapreduce and streaming,

    R. Kumar, B. Moseley, S. Vassilvitskii, and A. Vattani, “Fast greedy algorithms in mapreduce and streaming,” ACM Transactions on Parallel Computing, vol. 2, no. 3, pp. 1–22, 2015

    2015

  40. [48]

    Online DR-submodular maximization with stochastic cumulative constraints,

    P. S. Raut, O. Sadeghi, and M. Fazel, “Online DR-submodular maximization with stochastic cumulative constraints,” arXiv preprint arXiv:2005.14708, 2020

    2005 arXiv

  41. [49]

    MapReduce: simplified data processing on large clusters,

    J. Dean and S. Ghemawat, “MapReduce: simplified data processing on large clusters,” Commu- nications of the ACM, vol. 51, no. 1, pp. 107–113, 2008

    2008

  42. [50]

    Execution order matters in greedy algorithms with limited information,

    R. Konda, D. Grimsman, and J. R. Marden, “Execution order matters in greedy algorithms with limited information,” in American Control Conference, pp. 1305–1310, 2022

    2022

  43. [51]

    Distributed strategy selection: A submodular set function maxi- mization approach,

    N. Rezazadeh and S. S. Kia, “Distributed strategy selection: A submodular set function maxi- mization approach,” Automatica, vol. 153, p. 111000, 2023

    2023

  44. [52]

    Distributed submodular maximization with limited information,

    B. Gharesifard and S. Smith, “Distributed submodular maximization with limited information,” IEEE Transactions on Control of Network Systems, vol. 5, no. 4, pp. 1635–1645, 2018

    2018

  45. [53]

    Optimality gap of decentralized submodular maximization under prob- abilistic communication,

    J. Vendrell and S. Kia, “Optimality gap of decentralized submodular maximization under prob- abilistic communication,” in IEEE International Conference on Decision and Control , (Milan, Italy), 2024

    2024

  46. [54]

    Optimal algorithms for submodular maximization with distributed constraints,

    A. Robey, A. Adibi, B. Schlotfeldt, J. G. Pappas, and H. Hassani, “Optimal algorithms for submodular maximization with distributed constraints,”arXiv preprint arXiv:1909.13676, 2019

    1909 arXiv

  47. [55]

    Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection,

    A. Das and D. Kempe, “Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection,” arXiv preprint arXiv:1102.3975, 2011

    2011 arXiv

  48. [56]

    Maximizing monotone submodular functions over the integer lattice,

    T. Soma and Y . Yoshida, “Maximizing monotone submodular functions over the integer lattice,” Mathematical Programming, vol. 172, pp. 539–563, 2018

    2018

  49. [57]

    Randomized greedy sensor selection: Leveraging weak submodularity,

    A. Hashemi, M. Ghasemi, H. Vikalo, and U. Topcu, “Randomized greedy sensor selection: Leveraging weak submodularity,” IEEE Transactions on Automatic Control , vol. 66, no. 1, pp. 199–212, 2020

    2020

  50. [58]

    Controlled islanding via weak submodularity,

    Z. Liu, A. Clark, L. Bushnell, D. S. Kirschen, and R. Poovendran, “Controlled islanding via weak submodularity,”IEEE transactions on power systems, vol. 34, no. 3, pp. 1858–1868, 2018

    2018

  51. [59]

    Towards minimizing k-submodular functions,

    A. Huber and V . Kolmogorov, “Towards minimizing k-submodular functions,” inCombinatorial Optimization: Second International Symposium, (Athens, Greece), pp. 451–462, 2012

    2012

  52. [60]

    Maximizing k-submodular functions and beyond,

    J. Ward and S. ˇZivn`y, “Maximizing k-submodular functions and beyond,”ACM Transactions on Algorithms, vol. 12, no. 4, pp. 1–26, 2016

    2016

  53. [61]

    Accelerated greedy algorithms for maximizing submodular set functions,

    M. Minoux, “Accelerated greedy algorithms for maximizing submodular set functions,” in Op- timization Techniques(J. Stoer, ed.), (Berlin, Heidelberg), pp. 234–243, Springer Berlin Heidel- berg, 1978

    1978

  54. [62]

    Lazier than lazy greedy,

    B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. V ondr ´ak, and A. Krause, “Lazier than lazy greedy,” inProceedings of the AAAI Conference on Artificial Intelligence, 2015. 21 REFERENCES REFERENCES

    2015

  55. [63]

    A supermodularity-based di fferential privacy pre- serving algorithm for data anonymization,

    M. R. Fouad, K. Elbassioni, and E. Bertino, “A supermodularity-based di fferential privacy pre- serving algorithm for data anonymization,” IEEE Transactions on Knowledge and Data Engi- neering, vol. 26, no. 7, pp. 1591–1601, 2014

    2014

  56. [64]

    Distributed submodular maximization: trading performance for privacy,

    N. Rezazadeh and S. S. Kia, “Distributed submodular maximization: trading performance for privacy,” inIEEE International Conference on Decision and Control, pp. 5953–5958, 2022

    2022

  57. [65]

    Deep submodular functions: Definitions and learning,

    B. W. Dolhansky and J. A. Bilmes, “Deep submodular functions: Definitions and learning,” Advances in Neural Information Processing Systems, vol. 29, 2016

    2016

  58. [66]

    Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination,

    Z. Xu, H. Zhou, and V . Tzoumas, “Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination,” IEEE Robotics and Automation Letters, vol. 8, no. 4, pp. 2261–2268, 2023

    2023

  59. [67]

    Mixed-integer programming approaches to generalized submodular optimization and its applications,

    S. K ¨uc ¸¨ukyavuz and Q. Yu, “Mixed-integer programming approaches to generalized submodular optimization and its applications,” inTutorials in Operations Research: Advancing the Frontiers of OR/MS: From Methodologies to Applications, pp. 1–30, INFORMS, 2023

    2023

  60. [68]

    Adaptivity in adaptive submodularity,

    H. Esfandiari, A. Karbasi, and V . Mirrokni, “Adaptivity in adaptive submodularity,” in Confer- ence on Learning Theory, pp. 1823–1846, PMLR, 2021

    2021

  61. [69]

    Streaming submodular max- imization: Massive data summarization on the fly,

    A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause, “Streaming submodular max- imization: Massive data summarization on the fly,” in International Conference on Knowledge Discovery and Data Mining, pp. 671–680, 2014

    2014

  62. [70]

    Submodular reinforcement learning,

    M. Prajapat, M. Mutn `y, M. N. Zeilinger, and A. Krause, “Submodular reinforcement learning,” arXiv preprint arXiv:2307.13372, 2023

    2023 arXiv

  63. [71]

    Fairness in submodular max- imization over a matroid constraint,

    M. El Halabi, J. Tarnawski, A. Norouzi-Fard, and T.-D. Vuong, “Fairness in submodular max- imization over a matroid constraint,” in International Conference on Artificial Intelligence and Statistics, pp. 1027–1035, 2024. 22

    2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.