Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions

Victoria G. Crawford

REVIEW 4 major objections 4 minor 19 references

Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read A biased Pareto evolutionary algorithm matches stochastic greedy's O(n ln(1/ε)) query complexity for monotone submodular maximization while keeping a pool of solutions.

desk verdict Theorem 1's O(nP) PO analysis is a real step forward, but the paper's BPO guarantee in Theorem 2 rests on a reversed Chernoff inequality and is not proven as stated. read the letter →

arxiv 1908.01230 v5 pith:G45AUKIE submitted 2019-08-03 cs.DS

Victoria G. Crawford This is my paper · ORCID

classification cs.DS

keywords monotonesubmodularmaximizationParetooptimizationevolutionaryalgorithmcardinalityconstraintquerycomplexityapproximationratiostochasticgreedyChernoffbound

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

Monotone submodular maximization asks for a set of at most κ elements maximizing a monotone, submodular value oracle f. This paper proves that the Pareto optimization algorithm—an evolutionary method that keeps a pool of mutually non-dominating sets, trading off f-value against cardinality—reaches an expected (1−ε)(1−1/e) approximation for every cardinality constraint κ

What carries the argument

The load-bearing device is a cardinality counter ω that tracks the largest f-value available among pool sets of size at most ω. Each time the pool's best set at that cardinality is selected and mutation flips exactly one element of the optimal set A*, ω increments; the proof lower-bounds the expected best f-value at the tracked cardinality by (1−(1−1/|A*|)^ω′)f(A*), which at ω=κ gives the (1−1/e) factor. For the biased algorithms, a family of counters β_j with geometrically spaced thresholds H_j=e ln(1/ε)/ξ^j approximately tracks ω without knowing κ, and each counter increment is an i.i.d. Bernoulli success with probability p/⌈ln(P)/ln(1/ξ)⌉ (or p for the single-κ version). Chernoff's bound converts the expected success count into a high-probability statement that the tracked cardinality reaches κ within T iterations, and the law of total expectation converts that into the approximation guarantee.

What would settle it

Take ξ=1/2, κ=P−1, and large n; compute Tp/M with T as in Theorem 2 and compare it with H_qκ for the corresponding q. The claimed Chernoff step requires Tp/M ≥ 2H_qκ, but the asymptotic values are ≈2e ln(1/ε)n versus ≈2e ln(1/ε)P, which for P≈n makes the required number of successes equal to—not below half of—the mean. That calculation alone refutes the proof's concentration argument; an experiment counting actual iterations until κ-BPO reaches the promised ratio would show whether the theorem itself survives.

Watch

Extended reading notes

Core claim

The central discovery is that the slow part of earlier Pareto-optimization analyses was not the algorithm but the lens: waiting for the standard greedy algorithm to appear inside the random mutation process costs O($nP^{2}$) queries, whereas the same process probabilistically performs a random version of greedy—pick uniformly random elements of the optimal set, allowing repeats—which already has the (1−1/e) guarantee. Analyzing the expected time for this random-greedy process to reach κ cardinality inside PO yields O(nP ln(1/ε)) queries in expectation. Replacing uniform pool selection with a biased selector that concentrates mutations on the current best set at a tracked cardinality gives BPO and κ-BPO, whose successes are Bernoulli trials with probability p/M or p, respectively; Chernoff bounds then give the near-linear and linear query counts. The paper's claims include the explicit approximation ratios (1−ε)(1−1/e) for PO and (1−ε)(1−1/e−ε) for BPO and κ-BPO, for every κ<P (or a given κ), in expectation over the algorithm's randomness.

Load-bearing premise

The load-bearing premise of the BPO and κ-BPO query bounds is that the biased counter increments form independent Bernoulli trials whose expected total is at least twice the number of increments needed to push the tracked cardinality to κ; if that mean-to-threshold condition fails, the Chernoff step that supplies the high-probability event does not go through.

Editorial extensions

If this is right

For any instance SM(f,κ) with κ<P, PO now comes with a deterministic-time query bound O(nP ln(1/ε)) for an expected (1−ε)(1−1/e) approximation, so the previous O(nP^2) wall is removed.
BPO provides the same style of guarantee for all cardinality constraints simultaneously in O(n ln(P) ln(1/ε)) queries, so one run yields usable solutions for every κ<P.
κ-BPO matches stochastic greedy's O(n ln(1/ε)) query complexity for a fixed cardinality κ, while keeping the evolutionary pool property that allows early termination and continued improvement.
The stated results transfer to monotone γ-weakly submodular objectives with the 1−1/e factor replaced by 1−1/e^γ, per the paper's extension.
If the guarantees hold, evolutionary Pareto methods are no longer dominated by greedy methods in query complexity for monotone submodular maximization.

Reading between the lines

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

The random-greedy-within-mutation argument is structurally independent of the exact value of the cardinality constraint, which suggests the same O(nP ln(1/ε)) style bound could carry to other Pareto formulations, such as submodular cover or general cost constraints, whenever a suitable tracking variable exists.
The geometric threshold spacing in BPO effectively guesses κ up to a factor of ξ; one could test whether a different spacing, such as doubling instead of 1/ξ, yields the same query bound with fewer counters.
The proof's success-count condition implies a testable prediction: as κ approaches P, the constant in the O(n ln(1/ε)) bound for κ-BPO should degrade unless the threshold condition is repaired; running BPO with κ=P−1 and ξ=1/2 would reveal whether the observed query count stays linear or grows with P.

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.

Desk Editor's Note

read the letter

Two things you should know about arXiv:1908.01230. First, Theorem 1 is a genuine improvement: the Pareto optimization algorithm gets a (1-ε)(1-1/e) guarantee in O(nP ln(1/ε)) queries, removing a factor P from the previous O(nP²) analysis, and the proof technique—tracking an idealized stochastic-greedy process inside PO—is a nice departure from greedy-emulation arguments. The induction is coherent and the Chernoff step for PO checks out. This part is publishable. Second, the headline BPO result, Theorem 2, is not established. In the appendix's final Chernoff step, the paper bounds P(ΣY_i < H_κ) by P(ΣY_i < Tp/(2M)) using T ≥ 2ne ln(1/ε)M/p. That containment requires H_κ ≤ Tp/(2M), i.e., κ/ξ^q ≤ n. But Equation (2) gives ξ^q P < κ, hence κ/ξ^q > P. For P close to n (or n+1), that exceeds n; the inequality is backwards. Concretely, P = n = 1000, κ = 999, ξ = 1/2, ε = 0.01 gives H_κ ≈ 25,011 and Tp/(2M) ≈ 12,518; the actual binomial tail is around 0.43, not ≤ ε. The theorem explicitly allows this regime. Theorem 3 is also not proven—the main proof is left to the reader—so its O(n ln(1/ε)) claim is unsupported as written. The empirical section has labeling inconsistencies (plots say BPO where the text says κ-BPO), but that is minor compared to the analytic gap.

Credit where due: the paper is clearly written, the related work is fair, and the biased selection idea is worth further attention. But the load-bearing guarantee of the new algorithm is unproven. I'd send this to a serious referee, with the expectation of major revision: fix the Chernoff step (either restrict the theorem to a regime where the inequality holds, or find a different argument) and actually write out Theorem 3. If those repairs succeed, the paper becomes solid. As it stands, I would not rely on the BPO/κ-BPO claims.

This is a paper for researchers in evolutionary computation and submodular optimization. The PO result deserves citation; the BPO result needs a corrected analysis.

Referee Report

4 major / 4 minor

Summary. The paper studies monotone submodular maximization under a cardinality constraint. Its first contribution is a new analysis of the Pareto optimization algorithm PO, claimed to achieve a (1-epsilon)(1-1/e) approximation in expectation for every kappa < P in O(nP ln(1/epsilon)) queries, improving on the previous O(nP^2) analysis. The second contribution is a new algorithm BPO that uses a biased selection rule and is claimed to achieve a (1-epsilon)(1-1/e-epsilon) approximation in expectation for every kappa < P in O(n ln(P) ln(1/epsilon)) queries, matching the stochastic greedy algorithm's query complexity; a further specialization kappa-BPO is claimed to achieve the same ratio for a fixed kappa in O(n ln(1/epsilon)) queries. The paper also reports experiments on data summarization instances.

Significance. If the claims are correct, the paper would make a meaningful contribution: the PO analysis removes a factor P from the prior query complexity, and BPO would be, to my knowledge, the first evolutionary algorithm for monotone submodular maximization matching the stochastic greedy query complexity while maintaining a solution pool. The exposition is generally clear, the algorithms are given as pseudocode, and the empirical study supports the qualitative convergence behavior. However, the proof of the main BPO theorem contains a load-bearing error in the Chernoff application, and the proof of the kappa-BPO theorem is omitted; as a result the central claims for BPO and kappa-BPO are not established in the current manuscript.

major comments (4)

[Section 2.2, End of Proof of Theorem 2 (Appendix 5.2)] The Chernoff step reverses the required containment. The proof writes P(sum_i Y_i < H q * kappa) <= P(sum_i Y_i < Tp/(2M)), but this is valid only when H_q * kappa <= Tp/(2M). Substituting H_q = e ln(1/epsilon)/xi^q and using Eq. (2) gives H_q * kappa <= e ln(1/epsilon) P / xi, while T >= alpha n M with alpha = 2e ln(1/epsilon)/p yields Tp/(2M) >= e n ln(1/epsilon). For P close to n and xi < 1, the first quantity can exceed the second. Example: n = P = 1000, kappa = 999, xi = 1/2, epsilon = 0.01, p = 1 gives q = 1, M = 10, H_1 kappa ~= 25,011, but Tp/(2M) ~= 12,518, so the event {sum < Tp/(2M)} is a strict subset of {sum < H_1 kappa} and the displayed inequality has the wrong direction. The Chernoff bound therefore does not control the probability of event F, and the O(n ln(P) ln(1/epsilon)) query-complexity claim for BPO is not proved.
[Section 2.2, End of Proof of Theorem 2 (Appendix 5.2)] Even if the containment were repaired, the final probability bound is not epsilon. The chain concludes e^{-Tp/(8M)} <= epsilon with justification (c) that T >= 8 ln(n) M / p, but that only yields e^{-Tp/(8M)} <= 1/n. The theorem statement sets beta = 8/p, so the second term in T gives the 1/n bound, not an epsilon bound. The law-of-total-expectation step would then give a (1 - 1/n) factor instead of (1 - epsilon) unless one additionally assumes n >= 1/epsilon. This needs to be corrected either by changing the second term to 8 ln(1/epsilon) M / p or by modifying the theorem statement and proof accordingly.
[Section 2.2, Eq. (2)] The existence of q in {1,...,ceil(ln(P)/ln(1/xi))} satisfying xi^q P < |A*| <= xi^{q-1} P is not guaranteed for all parameters covered by Theorem 2. For example, P = 2, kappa = 1, xi = 1/2 gives M = ceil(ln 2 / ln 2) = 1, and q = 1 fails because xi^1 P = 1 is not strictly less than kappa = 1. More generally, the condition can fail whenever P/kappa is exactly a power of 1/xi and M is too small. Since Theorem 2 quantifies over all kappa < P and all xi in (0,1), the proof does not cover its stated parameter range.
[Section 2.3, Theorem 3] The proof of Theorem 3 is not written out ('details are left to the reader'). This is one of the paper's headline results, and given that the analogous proof for Theorem 2 has the technical problems described above, the omission is not acceptable. A self-contained proof of Theorem 3, including the Chernoff step with explicit constants, is needed before the result can be verified.

minor comments (4)

[Section 2.1, Lemma 4] The statement of Lemma 4 in the appendix says P(sum_i Y_i < kappa) <= 1/n, while the main text states the same lemma with the bound epsilon and the proof concludes epsilon. This inconsistency should be fixed.
[Appendix 5.2, Lemma 6 proof] The proof of Lemma 6 says the success probability is p, but the lemma statement and the algorithm give p/ceil(ln(P)/ln(1/xi)). The proof should state that the index j must equal q as well.
[Section 3, Figure 1] The text says the experiments evaluate PO and kappa-BPO, but the figure legends label a curve as 'BPO' rather than 'kappa-BPO'. This should be clarified.
[Abstract and Section 1.1] The abstract states the BPO guarantee as (1-epsilon)(1-1/e-epsilon) in one sentence and as (1-epsilon)(1-1/e) in another; the body consistently uses (1-epsilon)(1-1/e-epsilon). Please harmonize the wording.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the analysis is self-contained and benchmarked against external greedy results.

full rationale

The paper's derivation chain is self-contained. Theorem 1 is proven by a probability analysis of PO in which the approximation factor comes from an idealized random-greedy process plus Chernoff bounds, and the target ratio (1-1/e) is compared against the standard Nemhauser-Wolsey and stochastic greedy benchmarks rather than assumed. Theorem 2's BPO proof defines the biased counters with H_q = e ln(1/epsilon)/xi^q and treats biased selections as i.i.d. Bernoulli trials; this is algorithm design followed by probability bounds, not a restatement of the desired approximation ratio. No fitted parameter is renamed as a prediction, and no load-bearing uniqueness or ansatz result is imported from the author's prior work; the only self-citation (Crawford 2019) appears in a related-work list and is not used to justify any theorem. The Chernoff containment step highlighted by the skeptic is a possible parameter-range or proof error rather than circularity, because even if the inequality fails for parameters such as P close to n and xi close to 1, the target result is not used as an input to the derivation.

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

No fitted parameters. The only inputs are algorithmic hyperparameters (p, epsilon, xi, P, T) that the theorems quantify over. The analysis is against external greedy benchmarks.

assumptions (4)

domain assumption f is monotone submodular with f(empty set)=0 and is accessed through a value oracle.
Defines the problem class in Section 1, Problem 1; all theorems assume this.
standard math The standard Chernoff bound (Lemma 9) applies to sums of independent Bernoulli trials.
Used in the proofs of Lemma 4 and Theorem 2.
standard math For any kappa < P there exists q with xi^q P < kappa <= xi^{q-1} P.
Used to define omega = beta_q in Theorem 2; follows from the geometric partition of [1, P].
standard math The mutation lower bound (1 - 1/n)^(n-1) >= 1/e.
Used in Lemma 3 and Claim 4 to lower bound the success probability of a useful mutation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions." pith.science (2026). https://pith.science/paper/G45AUKIE

@misc{pith2026190801230,
  author       = {Pith},
  title        = {Pith review of: Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G45AUKIE}},
  note         = {Machine review of arXiv:1908.01230}
}

abstract

In this paper, the monotone submodular maximization problem (SM) is studied. SM is to find a subset of size $\kappa$ from a universe of size $n$ that maximizes a monotone submodular objective function $f$. We show using a novel analysis that the Pareto optimization algorithm achieves a worst-case ratio of $(1-\epsilon)(1-1/e)$ in expectation for every cardinality constraint $\kappa < P$, where $P\leq n+1$ is an input, in $O(nP\ln(1/\epsilon))$ queries of $f$. In addition, a novel evolutionary algorithm called the biased Pareto optimization algorithm, is proposed that achieves a worst-case ratio of $(1-\epsilon)(1-1/e)$ in expectation for every cardinality constraint $\kappa < P$ in $O(n\ln(P)\ln(1/\epsilon))$ queries of $f$. Further, the biased Pareto optimization algorithm can be modified in order to achieve a worst-case ratio of $(1-\epsilon)(1-1/e)$ in expectation for cardinality constraint $\kappa$ in $O(n\ln(1/\epsilon))$ queries of $f$. An empirical evaluation corroborates our theoretical analysis of the algorithms, as the algorithms exceed the stochastic greedy solution value at roughly when one would expect based upon our analysis.

Figures

Figures reproduced from arXiv: 1908.01230 by the authors.

**Figure 1.** In all plots the y-axis is normalized by the standard greedy value on the instance, and the x-axis is normalized by the number kn of evaluations required by the standard greedy algorithm. The dataset, objective, and value of κ are indicated in the caption of each subfigure. [Krizhevsky et al., 2009] each represented by a 3072 dimensional vector of pixels (CIFAR). For the objective f, we use: (i) The monotonic and s… view at source ↗

**Figure 2.** An illustration of the event E in the proof of Lemma 5. The line describes events on iterations of BPO starting at σ(t) and increasing to t. σ(t) is defined to be the iteration where ω was set to ωt−1. On iteration σ(t), ` is set to 0 (which prompts the increment of ω). Then ` is incremented from 0 to H on some subset of iterations in (σ(t) + 1, t] including t. ... ... σ(t) σ(t) + 1 r t − 1 t ` incremented to H and … view at source ↗

**Figure 3.** An illustration of the event F in the proof of Lemma 5. Event F is a sub-event of the event E, which is depicted in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

Streaming submodular maximization: massive data summarization on the ﬂy

[Badanidiyuru et al., 2014] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: massive data summarization on the ﬂy. In ACM SIGKDD Inter- national Conference on Knowledge Discovery and Data Mining (KDD),

work page 2014
[7]

Approxi- mating covering problems by randomized search heuristics using multi-objective models

[Friedrich et al., 2010] Tobias Friedrich, Jun He, Nils Heb- binghaus, Frank Neumann, and Carsten Witt. Approxi- mating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617–633,

work page 2010
[11]

De- terminantal point processes for machine learning.Founda- tions and Trends® in Machine Learning, 5(2–3):123–286,

[Kulesza et al., 2012] Alex Kulesza, Ben Taskar, et al. De- terminantal point processes for machine learning.Founda- tions and Trends® in Machine Learning, 5(2–3):123–286,

work page 2012
[17]

Subset Selection under Noise

[Qian et al., 2017] Chao Qian, Jing-cheng Shi, Yang Yu, Ke Tang, and Zhi-hua Zhou. Subset Selection under Noise. In Advances in Neural Information Processing Systems (NeurIPS),

work page 2017
[18]

Pareto op- timization for subset selection with dynamic cost con- straints

[Roostapour et al., 2019] Vahid Roostapour, Aneta Neu- mann, Frank Neumann, and Tobias Friedrich. Pareto op- timization for subset selection with dynamic cost con- straints. In AAAI Conference on Artiﬁcial Intelligence (AAAI),

work page 2019
[19]

Maximizing monotone submodular functions over the integer lattice

[Soma and Yoshida, 2016] Tasuku Soma and Yuichi Yoshida. Maximizing monotone submodular functions over the integer lattice. In International Conference on Integer Programming and Combinatorial Optimization (IPCO),

work page 2016
[1978]

Randomized local search, evolutionary algo- rithms, and the minimum spanning tree problem

[Neumann and Wegener, 2007] Frank Neumann and Ingo Wegener. Randomized local search, evolutionary algo- rithms, and the minimum spanning tree problem. Theo- retical Computer Science, 378(1):32–40,

work page 2007
[2002]

Distributed submodular maximization: Identifying representative ele- ments in massive data

[Mirzasoleiman et al., 2013] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative ele- ments in massive data. In Advances in Neural Information Processing Systems (NeurIPS),

work page 2013

Show all 19 references

[2003]

Learning multiple layers of features from tiny images

[Krizhevsky et al., 2009] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report, University of Toronto,

2009
[2009]

Maximizing the spread of inﬂuence through a so- cial network

[Kempe et al., 2003] David Kempe, Jon Kleinberg, and ´Eva Tardos. Maximizing the spread of inﬂuence through a so- cial network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146. ACM,

2003
[2010]

Finding groups in data: an introduction to cluster analysis, volume

[Kaufman and Rousseeuw, 2009] Leonard Kaufman and Pe- ter J Rousseeuw. Finding groups in data: an introduction to cluster analysis, volume

2009
[2011]

Maximizing submodular functions under ma- troid constraints by evolutionary algorithms

[Friedrich and Neumann, 2014] Tobias Friedrich and Frank Neumann. Maximizing submodular functions under ma- troid constraints by evolutionary algorithms. In Interna- tional Conference on Parallel Problem Solving from Na- ture (PPSN),

2014
[2012]

Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem

[Laumanns et al., 2002] Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, and Kalyanmoy Deb. Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In Interna- tional Conference on Parallel Problem Solving from Na- t...

2002
[2013]

Lazier Than Lazy Greedy

[Mirzasoleiman et al., 2015] Baharan Mirzasoleiman, Ash- winkumar Badanidiyuru, Amin Karbasi, Jan V ondrak, and Andreas Krause. Lazier Than Lazy Greedy. In AAAI Con- ference on Artiﬁcial Intelligence (AAAI),

2015
[2014]

Guaran- tees for greedy maximization of non-submodular functions with applications

[Bian et al., 2017] Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guaran- tees for greedy maximization of non-submodular functions with applications. InInternational Conference on Machine Learning (ICML),

2017
[2015]

Best Algorithms for Approximating the Maxi- mum of a Submodular Set Function

[Nemhauser and Wolsey, 1978] G L Nemhauser and L A Wolsey. Best Algorithms for Approximating the Maxi- mum of a Submodular Set Function. Mathematics of Op- erations Research, 3(3):177–188,

1978
[2017]

An efﬁcient evolutionary algorithm for subset selection with general cost constraints

[Bian et al., 2020] Chao Bian, Chao Feng, Chao Qian, and Yang Yu. An efﬁcient evolutionary algorithm for subset selection with general cost constraints. In AAAI Confer- ence on Artiﬁcial Intelligence (AAAI),

2020
[2019]

Submodular meets Spectral: Greedy Algorithms for Sub- set Selection, Sparse Approximation and Dictionary Se- lection

[Das and Kempe, 2011] Abhimanyu Das and David Kempe. Submodular meets Spectral: Greedy Algorithms for Sub- set Selection, Sparse Approximation and Dictionary Se- lection. Proceedings of the 28th International Conference on Machine Learning (ICML),

2011
[2020]

Crawford

[Crawford, 2019] Victoria G. Crawford. An efﬁcient evo- lutionary algorithm for minimum cost submodular cover. In International Joint Conference on Artiﬁcial Intelligence (IJCAI),

2019

Pith tools

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

[1] [1]

Streaming submodular maximization: massive data summarization on the ﬂy

[Badanidiyuru et al., 2014] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: massive data summarization on the ﬂy. In ACM SIGKDD Inter- national Conference on Knowledge Discovery and Data Mining (KDD),

work page 2014

[2] [7]

Approxi- mating covering problems by randomized search heuristics using multi-objective models

[Friedrich et al., 2010] Tobias Friedrich, Jun He, Nils Heb- binghaus, Frank Neumann, and Carsten Witt. Approxi- mating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617–633,

work page 2010

[3] [11]

De- terminantal point processes for machine learning.Founda- tions and Trends® in Machine Learning, 5(2–3):123–286,

[Kulesza et al., 2012] Alex Kulesza, Ben Taskar, et al. De- terminantal point processes for machine learning.Founda- tions and Trends® in Machine Learning, 5(2–3):123–286,

work page 2012

[4] [17]

Subset Selection under Noise

[Qian et al., 2017] Chao Qian, Jing-cheng Shi, Yang Yu, Ke Tang, and Zhi-hua Zhou. Subset Selection under Noise. In Advances in Neural Information Processing Systems (NeurIPS),

work page 2017

[5] [18]

Pareto op- timization for subset selection with dynamic cost con- straints

[Roostapour et al., 2019] Vahid Roostapour, Aneta Neu- mann, Frank Neumann, and Tobias Friedrich. Pareto op- timization for subset selection with dynamic cost con- straints. In AAAI Conference on Artiﬁcial Intelligence (AAAI),

work page 2019

[6] [19]

Maximizing monotone submodular functions over the integer lattice

[Soma and Yoshida, 2016] Tasuku Soma and Yuichi Yoshida. Maximizing monotone submodular functions over the integer lattice. In International Conference on Integer Programming and Combinatorial Optimization (IPCO),

work page 2016

[7] [1978]

Randomized local search, evolutionary algo- rithms, and the minimum spanning tree problem

[Neumann and Wegener, 2007] Frank Neumann and Ingo Wegener. Randomized local search, evolutionary algo- rithms, and the minimum spanning tree problem. Theo- retical Computer Science, 378(1):32–40,

work page 2007

[8] [2002]

Distributed submodular maximization: Identifying representative ele- ments in massive data

[Mirzasoleiman et al., 2013] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative ele- ments in massive data. In Advances in Neural Information Processing Systems (NeurIPS),

work page 2013