Improved Theoretically-Grounded Evolutionary Algorithms for Subset Selection with a Linear Cost Constraint
Authors: Dan-Xuan Liu
Chao Qian
Venue: ICML 2025 poster (2025)
Keywords: submodular optimization
linear constraints
multi-objective evolutionary algorithms
Primary area: optimization->discrete_and_combinatorial_optimization

Abstract: The subset selection problem with a monotone and submodular objective function under a linear cost constraint has wide applications, such as maximum coverage, influence maximization, and feature selection, just to name a few. Various greedy algorithms have been proposed with good performance both theoretically and empirically. Recently, evolutionary algorithms (EAs), inspired by Darwin's evolution theory, have emerged as a prominent methodology, offering both empirical advantages and theoretical guarantees. Among these, the multi-objective EA, POMC, has demonstrated the best empirical performance to date, achieving an approximation guarantee of $(1/2)(1-1/e)$. However, there remains a gap in the approximation bounds of EAs compared to greedy algorithms, and their full theoretical potential is yet to be realized. In this paper, we re-analyze the approximation performance of POMC theoretically, and derive an improved guarantee of $1/2$, which thus provides theoretical justification for its encouraging empirical performance. Furthermore, we propose a novel multi-objective EA, EPOL, which not only achieves the best-known practical approximation guarantee of $0.6174$, but also delivers superior empirical performance in applications of maximum coverage and influence maximization. We hope this work can help better solving the subset selection problem, but also enhance our theoretical understanding of EAs.

Improved Theoretically-Grondeee Evolutionary Algorithms for Subset Selection with a Linear Cost Constraint
Dan-Xuan Liu 12
Chao Qian
Abstract
tion f. while the cost of the subset X must not exceed given budget B. This fundamental problem is NP-hard and arises in diverse domains involving cost-aware resource al- location, including combinatorial optimization, computer networks, data mining, and machine learning. Potential ap- plications include maximum coverage (Feige, 1998), maxi- mizing coverage under budget constraints; influence max- imization (Kempe et al., 2003), maximizing social influ- ence spread under budget constraints; sensor placement, balancing information gain with installation costs (Krause et al., 2006); recommendation systems, promoting prod- ucts within advertising budgets while respecting user prefer- ences (Ashkan al., 2015); unsupervised feature selection, optimizing reconstruction error of data matrix under fea- resource constraints (Feng et al., 2019); active learning, selecting maximally informative data samples under limited annotation budgets (Golovin & Krause, 201 1); and human- assisted learning, optimizing machine learning models with limited expert resources (De et al., 2020; Liu et al., 2023).
The subset selection problem with a monotone and submodular objective function under a lin- ear cost constraint has wide applications, such as maximum coverage, influence maximization, and feature selection, just name a few. Various greedy algorithms have been proposed with good performance both theoretically and empirically. Recently, evolutionary algorithms (EAs), inspired by Darwin's evolution theory, have emerged as prominent methodology, offering both em- pirical advantages and theoretical guarantees. Among these, the multi-objective EA, POMC, has demonstrated the best empirical performance date, achieving an approximation guarantee of (1/2)(1 - 1/e). However, there remains a gap in the approximation bounds of EAs compared to greedy algorithms, and their full theoretical potential is yet be realized. In this paper, we re- analyze the approximation performance of POMC theoretically, and derive improved guarantee of 1/2, which thus provides theoretical justification for its encouraging empirical performance. Fur- thermore, we propose a novel multi-objective EA,, EPOL, which not only achieves the best-known practical approximation guarantee of 0.6174, but also delivers superior empirical performance in applications of maximum coverage and influence maximization. We hope this work can help bet- ter solving the subset selection problem, but also enhance our theoretical understanding of EAs.
By introducing monotonicity and submodularity. the algo- rithms with theoretical guarantees for subset selection have been well studied. A set function f is monotone (typi- cally non-decreasing) if it does not decrease with the ad- dition of items to set. A set function f is submodular if VX C Y,U u E Y f(X vv f(x) 2 implying the diminishing returns property (Nemhauser et al., 1978). this paper, we focus on the subset selection prob- lem as follows:
arg max f(X) s.t. c(X) = Σ S Xgv
(1)
VEX
where the objective function f: R monotone and submodular, and the cost function e 2 + R lincar. For the special case c(X) = | < B, a simple greedy algo- rithm achieves the optimal polynomial-tin approximation guarantee of 1/e (Nemhauser al., 1978).
1. Introduction
The subset selection problem aims to select a subset X from a given ground set V that maximizes a specific func-
'National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China "School of Artificial Intelligence, Nanjing University, Nanjing 210023, China. Corre- spondence to: Chao Qian <qianc <uinniiiccnnuu..du..o.o nju.cedu.n>>..
For the general problem presented in Eq. (1) with lin- ear cost constraint, greedy algorithms also mainstream algorithms, and many variants have been proposed. The Generalized Greedy Algorithm (GGA) iteratively selects an item maximizing the ratio the increment on f and c, achieving a (1/2)(1 - 1/e) ze 1..2-approximation ra- (Krause & Guestrin, 2005), which was further improved
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Theoreticall-Groondeed Evolutionary Algorithms for Subset Selection with Linear Cost Constraint
to - 1/Vē as 0.39 (Lin & Bilmes, 2010). Another greedy algorithm, Greedy,. : extends GGA by considering addi- tional single-item expansions of all intermediate solutions, achieving a better approximation ratio of 0.5 (Yaroslavt- sev et al., 2020). The 1-guess-Greedy+* variant further improves this approach, reaching an impressive approxi- mation ratio of 0.6174, by merely executing a single partial enumeration step. While there are greedy algorithms that obtain the theoretical optimal approximation of 1 1/e,, they are generally impractical due to high computational costs. Sviridenko (2004) developed a (1 app)oxappoii algorithm by selecting three optimal elements and using a greedy approach, which, however, has a high time com- plexity of (nn)), where n = [V] is the size of the ground set V. Later, Badanidiyuru & Vondrák (2014) and Ene & Nguyen (2019) proposed greedy-based algorithms that achieve (1 - 1/e c) -)approximation, where e > O. However, their computational costs remain prohibitively high, with time complexities of (n² (lon ( )0(1/-9) and
ning time of O(n² For more EAs with theoretical guarantees for cost function mapping to non-negative inte- gers instead of reals, i.e., 2 + N, please see (Neumann & Witt, 2023; Neumann & Rudolph, 2024). Among these EAs, POMC achieves the best experimental results (Roost- apour et al., 2022). Table 1 provides a summary of the practical algorithms for the subset selection problem consid- ered in Eq. (1). Note that there have also developed a series of EAs with theoretical guarantees for diverse variants of subset selection, e.g., (Qian et al., 201 5a; 2016; 201 7b;c; 2018; 2020; Bian et al., 2022; Liu & Qian, 2024; Qian et al., 2017d; 2019; Qian, 2020; 2021: Qian et al., 2022; 2023)
Despite exhibiting the best empirical performance, POMC still has gaps in approximation ratios compared to other algorithms. Thus, an interesting question whether the currently- approximation ratio of POMC is tight. To further explore the potential of EAs, can we design EAs better than POMC both theoretically and empirically? In this paper, we try to address these questions and make the following contributions:
(1/e)00/e")) log" n. respectively. These complexities ren- der the algorithms impractical for real-world applications. For additional unique algorithmic approaches, please refer to (Tang et al., 2022; Kulik et al., 2021: Li et al., 2022).
Through a refined analysis of the lower bound for improving f(X) by adding a specific item to X, we improve the approximation ratio of POMC from (1/2)(1- - 1/e) to 1/2 in Theorem 3.1.
Since greedy algorithms may get trapped in local optima, evolutionary algorithms (FAs), inspired by Darwin's 's theory of evolution, have been recently applied to subset selec- tion (Zhou et al., 2019). They are general-purpose random- ized heuristic optimization algorithms (Bäck, 1996) that mimic variational reproduction and natural selection. Start- ing from an initial population of solutions, EAs iteratively improve solutions by employing global-search operators such as mutation. They have achieved superior empirical performance than greedy algorithms, while also ensuring theoretical guarantees. Qian et al. (2017a) proposed a simple oblti-objeeetve EA named POMC to maximize f and mini- mize e simultaneously, which can achieve an approximation ratio of (1/2) 1/e). using OnnBPmax/8 /8) expected running time!, where Pmaz is the largest size of population during the running of POMC, and 8 millge e(v) is the minimum cost of any item in V. EAMC (Bian et al., 2020) and EVO-SMC (Zhu et al., 2024) are single-objective EAs for subset selection. They are guided by surrogate func- tions of integrating / and e, and maintain a limited number of solutions for each possible subset size. They ensure approximation ratios of (1/2)(1 1/e) and 0.5, respec- tively, using Onn² KB) expected rumning time, where K denotes the largest size of a subset satisfying the constraint c(X)= < B. FPOMC (Bian et al., 2021) modifies POMC by introducing a greedy selection strategy and also achieves a (1/2)(1 - approxxiiiiiiiaooo ratio with an expected run-
We propose a new multi-objective EA called EPOL, which achieves an approximation ratio of 0.6174 (The- orem 4.1,, using O(n² BP mmaz/ expected running time. EPOL is easily parallelizable, and the expected running time can be reduced to O(n Pmoz/// /5), the
same as that of POMC.
Experiments across various settings of the applications of maximum coverage and influence maximization vali- date the best performance of POMC among all existing algorithms, and show that EPOL can further improve the performance significantly in almost all cases.
2. Preliminaries
Let IR and R+ denote the set of reals and non-negative reals, respectively. The set V = [11, U2,..., En denotes a ground set. A set function ʃ : 2 + R is monotone if VX C : f(x) < f(Y). The submodularity represents the diminishing returns property (Nemhauser et al., 1978), i.e., adding an item to a set X gives a larger benefit than adding the same item superset Y of X. A set function f : 2 + IR is submodular if XA C Y C V,u $ Y.
f(XUv) - f(x)= 2 (Y - f(Y);
(2)
'The expected running time refers to the expected number of evaluations of the objective function, as objective evaluation is usually the most expensive part of the algorithmic process.
or equivalently for any X CV.V.
((Y) 1(x))(X)>Een)) (((XUt) (1))))))))
(3)
2

---

Improved Theoretically-Gromdde Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Table 1. Summary of practical algorithms (with approximation guarantees and running time) for the subset selection problem in Eq. (1).
Algorithm
Guarantee
Running time
GGA (Krause & Guestrin, 2005)
(1/2) - 1/e) se 0.32
O
GGA (Lin Bilmes, 2010)
1 1/Ve 0.39 0.5 0.6174
OnKBB)
Greedy algorithms
Greedy+ (Yaroslavtsev et al., 2020)
O(nKa)
1 I-guess-Greedy" (Feldman et al., 2023)
O Kn)
POMC (Qian et al., 2017a)
(1/2) 100(111///
OnnBPuad ())
EAMC (Bian et al., 2020)
(1/2)
O(n²Kn)
FPOMC (Bian al., 2021)
(1/2)
O O(n²KB)
Evolutionary algorithms
EVO-SMC (Zhu et al., 2024)
0.5
POMC (this paper)
0.5
O(nBPmaac mazz/ 00)
EPOL (this paper)
0.6174
O BPinaz) /0)
Note that we represent a set {u} with a single element as e.
to 0.5 (Yaroslavtsev et al., 2020). Recently, a practical greedy algorithm named aggues-GGredyy was proposed. By performing single partial enumeration on the existing Greedy algorithm, it achieves approximation ratio of 0.6174, which is impressively close to the optimal approxi- mation ratio of 1/c = 0.632 (Feldman et al., 2023).
Our studied problem as presented in Definition 2.1 is to maximize monotone objective function ʃ with linear cost function We assume w.l.o.g. that monotone functions are normalized, i.e., f(0) = 0.
Definition 2.1 (Subset Selection with a Linear Cost Con- straint). Given a monotone submodular objective function and
2.1.2. POMC ALGORITHM
f: 2 + RR linear cost function c: 2 + R+
budget B, find
The performance of greedy algorithms may be limited due to the greedy nature. This motivates the design of series of EAs (Qian et al., 2017a; Bian et al., 2020; 2021; Roostapour et al., 2022; Neumann & Witt, 2023; Neumann & Rudolph, 2024; Zhu et al., 2024), trying to obtain better optimization abilities for subset selection. Based on Pareto Optimiza- tion (Friedrich & Neumann, 2015; Qian el al., 2015b), Qian et al. (2017a) proposed a multi objett-oeecttive EA, POMC, for subset selection. represents subset X C V by Boolean vector æ {0, 1)",, where the i-th bit r; 1 iff v; E X. We will not distinguish æ E {0, and its corresponding subset {up Vl 1} for notational convenience. POMC reformulates the original problem Eq. (4) as bi-objective maximization problem
arg maxxcv xgV ((X) s.t. cxx)= E
vEX dU) (4)
2.1. Previous Algorithms
We now introduce practical greedy algorithms for the problem defined in Definition 2.1, including I-guess- Greedy+ (Feldman et al., 2023), which achieves the best- known practical approximation ratio of 0.6174, close to the optimal ratio of 1 - 1/e /e= x 0.632. In addition, we in- troduce POMC, an EA that has demonstrated advantages in experiments and achieves an approximation ratio of (1/2)(1 - 1/e) R 0.32.
2.1.1. GREEDY ALGORIHMS
arg max (fi(a),, f2(x)),
(5)
Generalized Greedy Algorithm (GGA) (Zhang & Vorobey- chik, 2016) iteratively selects item that maximizes the ratio of marginal gain on f to cost c, until reaching the cost budget B. The algorithm finally outputs the better of two candidates: the subset X; found by the greedy process or the best single item. GGA achieves a (1/2) 1/e) 0.32- approximation ratio (Krause & Guestrin, 2005), which was 1/Ve 0.39 (Lin & Bilmes, 2010). An alternative greedy algorithm, called Greedy (Yaroslavt- sev et al., 2020), extends GGA by considering solutions formed by adding a single item to all generated subsets X, in the iterative process. Specifically, Greedy+ outputs the best solution in (X, (X, Uološis i, ve A c(x, Uv) s B). This modification improves the approximation ratio
--c, <(x) >
where fi(x)
fz(x) -((x).
(ax), otherwise
That is, POMC maximizes the objective function and minimizes the cost function e simultaneously. The solu- tions with cost values larger than B (i.e., c(x) > B) are excluded by setting their f1 values to -oc. Under the bi- objective formulation, two solutions are compared based on the domination relationship.
later improved
Definition 2.2 (Domination). For two solutions æ and x',
x weakly dominates x', denoted as x 2 x', if fi) 2 fi (x') A fz(œ) 2 fe(x'); x dominates x'. denoted x > x', or t ar' and either
3

---

Improved Theoretically-Gromnii Evolutionary Algorithms for Subset Selection with Linear Cost Constraint
Algorithm 1 POMC (V, J. c, B)
better empirical performance, as stated in Sections and 4, respectively. We will show their superior performance on two real-world applications in Section 5.
Input: ground set V with n items, a monotone submodular function f. a linear cost function c, a budget B
Output: solution x E {0,1)* with c(ar) S B Process:
3. Improved 1 1/2-Approimmation of POMC
1: Reformulate the original problem in Eq. (4) to the bi- objective problem (f)) f2())) in Eq. (5);
In this section, we re-analyze the approximation ratio of POMC, improving the previously known (1/2)(1 1/e) in Theorem 2.3 to 1/2 in Theorem 3.1. Let og be the item from the optimal solution X with the maximum cost, i.e., Oe E arg max c(v).
2: Let æ = 0", P {æ)):
3: repeat
4: Select æ from P uniformly at random;
5: Generate x' by flipping each bit of x with prob. 1/n;
6: if 1) E P such that z > x' then
Theorem 3.1. For the problem in Definition 2.1, POMC with at most enBPmoz! / expected number of iterations finds subset X S such that c(X) S. B and
7: P= (P f= E P x' = x}) {2'}
8: end if
9: until some criterion met
f(X) (1/2) f(x*).
10:
return arg B (ax)
Previous analysis of POMC used a coarse-grained manner to evaluate the lower bound on improving f(X) (Qian et al., 2017a). This led to POMC being able to derive solution X1 that satisfies f(X,) 2 (1 (1e)/))-/o ((X"), which is, how- ever, infeasible, i.e., c(X,) > B. A connection was then established between X1 and two feasible solutions X and Y. demonstrating that max f(Y)} 2 f(X1)/2 2 (1/2) - 1/e) f(X)). This weakens the tightness of the bound. In contrast, our analysis adopts a fine-grained approach, inspired by the analysis of Greedy+ (Yaroslavt- sev et al., 2020) and 1-Guess-Greedye 2023), to evaluate the lower bound on improving f(X), leading to that POMC can find a feasible solution X₂ with f(X2) 2 (1X2)-f(X*) and c(X2) E (B (B-c(0n c(o2). BJ. Then, we give the detailed proof of Theorem 3.1, which relies on Lemma 3.2, showing that POMC can obtain an approxima- tion ratio of z(r) within at most ennPmarr/ / number of iterations. This approximation ratio, i.e., 1 1- (r), based on special function 2(-) described in Lemma 3.4, where r fox)) f(x)) will also be used in the analysis of the proposed EPOL algorithm in Section 4.
f(()) > fi(z') or f2(2) > f2(2');
they are incomparable if neither x ž x' nor x x.
To solve the bi-objective maximization problem Eq. (5), POMC employs simple multi-objeccive EA in lines 2-9 of Algorithm 1, inspired by the GSEMO algorithm (Laumanns et al., 2004). It starts from the empty set 0 (line 2), and repeatedly improves the quality of solutions in the popula- tion P (lines 3-9). In each iteration, a parent solution æ is selected from P uniformly random (line 4); then an off- spring solution x' is generated by flipping each bit of with probability 1/n (line 5), which is used to update the popu- lation P (line 6 8). If x is not dominated by any solution in P (line 6), it will be added into P, and meanwhile, those solutions weakly dominated by x' will be deleted (line 7). This ensures that P contains only incomparable solutions. After terminated, it returns the best feasible solution with the largest value in the population (line 10).
(Feldman et al.,
expected
Qian et al. (2017a) proved that POMC achieves an approx- imation ratio of (1/2) 1/e) with at most en Bn m expected number of iterations, where Pinax is the largest population size during the running of POMC, and â = minngy c(v) is the minimum item cost the ground set V. Theorem 2.3. (Qian et al., 2017a) For the problem in Defini- tion 2.1, POMC with at most enBP Pmna/ 1 expected number of iterations finds a subset X C V such that c(X)= S B and
Lemma 3.2. Define r as f(x)) Ifr S 1/2, POMC with at most enB enBPPno/ 1 expected number of iterations finds subset X C V with c(X) S B and
f(x) 2 (1 ( 2(r)) f(x*),
where 2(-) is a special function described in Lemma 3.4.
Lemma 3.2 builds on Lemmas 3.3 and 3.4. Specifically, Lemma 3.3 shows a lower bound on improving f(X) by adding a specific item to X. The improvement is expressed as a weighted combination of f(X") - f(X U oc) and f(X*) - f(X)- f(r), scaled by the cost c(u*) and nor- malized by the budget B - c(or). Its proof is provided in Appendix A due to space limitation. Lemma 3.4 estab- lishes an one-to-one correspondence between the expres- sions r/²(r) - and In(x(r)/(1 - r)), as defined by the unique value 2(r).
f(X) Z (1/2)(1 1/e) f(x"),
where X* is an optimul solution.
Though the approximation ratio has gaps compared to other algorithms, POMC achieves the best emprical per- formance (Roostapour et al., 2022). This work aims to improve the approximation bound of POMC, and design a more advanced EA with stronger theoretical guarantees and
4

---

Improved Theoretically-roondde Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Lemma 3.3. For any subset X C V such that the lotal cost c(X) S B -c(oe), where Oc arg maxvex. d(v), there exists a solution X' = UU that satisfies
Case 1: Assume that J(X U < (1 - -r)) s(X)) Because Jmaz S B c(o=), the corresponding solution X must satisfy c(X) S B - c(o.). According to Lemma 3.3, by flipping one specific 0-bit of X, i.e. adding an item o' E arg XxXxxxx s(XUv)-((X) we can generate c(w)
(1 a) do²)
- F(x)-
2
B c(oo)
a new solution X' = - such that
+ a: )
B (o,) (f(X*) -f(o)) - f(X))
(1 (1-a) (F(X))-((XUo)))
f(x)) 2
B c(oo)
where v² E arg max ((XU)))
((X) and a E 10.1]. d()
a d(-))
+ B c(oc)
(f(x*) - -f(oc) -f(x))
Lemma 3.4 (Lemma 4 in (Feldman et al., 2023)). For every r E [0, 1/2], there is a unique value 2(r) E [r, 1/2] satisfy- ing the equation r/z(r) - 1 = In(2(r)/ - r)) E [-1,0].
2 (1 a) . d(v")
B B- d(c)) =x())_((x*))
Moreover, z(r) is a non-decreasing function T.
a.c(v")
+ B-c(oc)
((oo)
The proof of Lemma 3.2 defines Jmax the largest j in [0, B- c(oz)] for which subset X E P satisfying x(x) S j and f(X) meets a threshold that increases with j. The process iteratively updates the value of Jmas by applying Lemma 3.3 until a subset achieves the desired ap- proximation level. Additionally, it analyzes the expected number of iterations required to achieve each successive improvement in Jmas:
where a E 10, 1] and the last inequality holds by the assump- tion that f(X U oz) < (1 - z(r)) f(x*).
Eq. (6) consists of two terms added together, where the min(s.J)
first term is (1 - e B- (f(x*) - f(oo)) and the
second term is max(i-J =(r) -(X*). When s B B-o(oe)
J, the second term in Eq. (6) equals zero. Conversely, when i J. the first term becomes constant value, (1 ---e E xーPveT 2 contributes B-e(os) f(X*) Next, we analyze f(X) by considering the relationships among i, i + c(u"), and J.
Proof of Lemma 3.2. We analyze the increase of quantity Jmaa during the process of POMC, which is defined as
[- (f(x*) - f(oo)). while the second term
J Jmaz= = max E [0, c(o:)] 3X P,((X) jA (f(x*)
f(x) 2 (1 - E min( + max (j - J,0}
(1) When i + c(u*)= S J, applying Eq. (6) to Eq. (7) and setting a = 1, we get
- 2(()) . -(x")),
B - Bc.)o))
clu*)
S(x') 2 (1 - -11 B - c(0c)
.e B -d-0)))
where r- = fXx') < 1/2, and J = -BB c(o.))
In s(r) T- E [0, B c(o=)) according to Lemma 3.4.
([(X)) - -((o))
(8)
:la(0") 2 (1 (1-e- B B-ttve
- -J(X*) -
The initial value of Jaa is O, since POMC starts from the all-Os solution 0", representing an empty set. Assume that currently Jmez= = i v B- - c(o.) and X is corresponding solution with the value i, i.e., c(x) Si < B- - c(oo) and
where the last inequality holds by 1+x5
(2) When J (i, +c((")) applying Eq. (6) to Eq. (7), and
setting a = (J-i)/c(u") < <,, a c(p'')())) J, we get
(in( B-oloe)
((X) 2 (1 -
) (J(X*) - ((o))
imove("")
m J,0]
(6)
f(X)= 2 (1 - B-oloo)
(f(x*) f(oo))
2(r) - f(x*). B c
+ (1 (1-a). c(("")
2(1)
B - c(0e)
(9)
We first show that Jmaz cannot decrease. If X is kept in P, Jmaz obviously will not decrease. If X is deleted from P (line 7 of Algorithm 1), the newly included solution X' must weakly dominate X, i.e., f(X)= 2 f(X) and c(X') < c(X), implying Jmaz 2 i.
= =Cst + i i c(u") - J
z(r): [(X"),
B c(oc)
where Cst denotes the constant value Ost = (1
B yoo)) (f(X*) ff(o)).
Next, we show that within en emPmax expected number of iterations, either Jmaz can increase by at least ò or (1- appro-aaprooimmation solution can be generated, where 8 = mingey c(v) and Pmaz is the largest size of the population P during the execution of POMC.
(3) When J < i. applying Eq. (6) to Eq. (7) and setting
a = O, we get
f(x') 2 Cst + i (+(("))= J
x(r)) f(x"). (10)
B 3 d(o)))
5

---

Improved Theoreticaly--Gromdde Evolutionary Algorithms for Subset Selection with Linear Cost Constraint
By combining the inequalities derived from cases (1) to (3),
where the first inequality holds by applying Eqs. (9) and (10)
i.e. Eqs. (8) to (10), we can conclude that the new solution
because J = -(B - -((o)) In +|m2 < B - -(o) < Jmax + c(u"), the second inequality holds by Jmaz + (v')
X" = XXUUU U satisfies:
B
f(x') 2 (1-e e m
c(o.), the first equality holds by Cst = (1 11-66 -- z(r)
B-c(os)
(f(x*)- - -(oo))
J = -(B - -c(o)) In I-p; and In air) z(r) - by Lemma 3.4, and the last equality derived from the fact that r = f(o))/
- (
i-
maxfi- c(ut) J,0} 2(r) - f((*).
B - ((o)
The solution X' is feasible, because c(X') - Jmaz + c(o") I B - c(oo) + c(o.) = B. Once X' is produced, P will always contain a (1 app)oapppoinnntioonn solution. To achieve this, requires at most B- ennmma ten Pmr I en enBPPmac mana/ /8 expected number of iterations. Thus, the lemma holds.
Additionally, the cost of solution X' satisfies c(X') = c(X) - -c(o") S + c(v"). Consequently, the solution X" must be included in P; otherwise. X' must be dominated by one solution in P (line 6 of Algorithm 1). This implies that Jmas has already exceeded i, contradicting the assumption that J Jaa = i. Hence, after including X', we have Jmaz 2 i + c(u*). Since c(v²)= 2 8, it follows that Jmaz 2 i + 6. Thus, Jmaz can increase by at least 5 in one iteration with
The proof of Theorem 3.1 proceeds by analyzing two cases. In each case, 1 1/2-approximation solution is achieved. The final result is obtained by taking the maximum of the ex- pected number of iterations required for the two cases.
probability at least Piaz= _ (1- 7 ) 2 enP'max' where Pinar is lower bound the probability of selecting X (line 4), and (1 - -- is the probability of flipping a specific bit while keeping other bits unchanged (line 5). Therefore, it needs at most enPmaz expected number of iterations increase Jma by at least 8.
Proof of Theorem 3.1. Lemma 3.2 has shown that when r = floe)/((X)) & 1/2, POMC can find a feasible solu- tion X in the population P satisfying fXX) 2 - - - s(X"), using most enBPP maz/0 expected number of it- erations. According Lemma 3.4, the function =(r) has upper bound 1/2 when E [0, 1/2). Then we have f(X) 2 (1 - 2(r)) f(x) 2 (1/2) f(x*).
Case 2: If J(X U.) < (1 (1-20 (r)) f(x*) does not hold, it implies that X Uo is feasible solution with (1 - =(r)-- approximation, i.e., c(X U 0.)= Sit si+c(os c(os) S B and
When f(oa)/((X*) > 1/2, it implies that the solution with a single item o satisfying f(o.) > (1/2)-((X') Note that 0 always exists in P. since it has the smallest cost. Thus, the subset oe (an abbreviation of {oc}) can be generated in one iteration by selecting 0" in line 4 of Algorithm I and flipping only the corresponding 0-bit in line 5, whose probability is at least - (1- 2 2 en Pmaa That is, og will be generated in at most en Pmar expected number of iterations. According to the updating procedure of P (lines 6-8), we know that once the subset og is produced, P will always contain a 1/2-approximation solution.
s(XUa)) 2 (1 =(r))- 1(x))
The solution X U De can be generated in one iteration by selecting X in line 4 and flipping only the O-bit correspond- ing to the item Oe in line 5, whose probability is at least Piaz 11 2 2 emPmas That is, X U Oe will be generated in at most enP maz iterations in expectation. According to the updating procedure of P (lines 6-8), we know that once X U o. is produced, P will always contain a solution Z > X oc, i.e., c()) S c(X U Uc))= S B and f(2) Z f(X U..) 2 (1 - (r)) f(x*).
Taking the maximum of the expected number of iterations of the above two cases, POMC uses at most enB en.Pmaaz/ P /8 expected number of iterations, to find a 1 1/2-approximation solution. Thus, the theorem holds.
We have shown that when Jmaz S B c(oc). either Jmax can increase by least ō or a (1 (r))))(pproop approximation solution can be generated within enPP iterations in ex- pectation. The latter implies that the theorem already holds. We now focus on the state where the inclusion of the new so- lution X' causes Jmaz + c(ve) to exceed B- - c(Oc). Specif- ically, we consider the case where Jmaz 5 B- c(oc)= < Jmax + c(v"), which leads to
4. Proposed EPOL with 0.61 0.6174-Approximatie
In this section, we propose an Enhanced Pareto Optimization method for maximizing monotone submodular function with a Linear cost constraint in Definition 2.1, briefly called EPOL. As described in Algorithm 2, EPOL divides the original problem (V, f, c, B) into several residual problems, that is, for each e E V, it creates a residual problem (V \ f( u), B c(F)). where f(: o) =
J Jman + c(v") J 2(r) f(x*)
f(X') 2 Ost +
B- - cooo)
B c(o.) J
2 Cst +
B - c(0c) 2()) - -(x")
- f(v), and then solves these residual problems by running POMC (line 3). EPOL combines the output solution X, of each residual problem (V \ u. f( v),c, B - c(r)) with v to
2(rr)
= (1 1 1-,) ) (f(x*) f(o.)) +r. f(X*)
= (1- - 2(r)) f(X")
6

---

Improved Theoretically-roonnde Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Algorithm 2 EPOL Algorithm
Case 2: We analyze the case where f(oy) < (1/3)-
Input: ground set V with r items, a monotone submodular objective function f. a linear cost function c, budget B Output: solution X Ç V with c(X) 1 B
Let og be the item in X Os with the maximum cost, ie., d' E arg max Mly c(v), which implies f(o') S f(or). By the submodularity (i.e., Eq. (2)) of f. we have 5(X* of) - -(0) 2 f(X)) - f(oy). It follows that
Process:
1: Q 0:
[(0') S Mor)
2: for in V do
f(x* \(x+ -(x*)-fie f(og) $1/2.
(1))
3: X f POMC(V) \ v,
4: Q Qx,
5: end for
Let r't = s(d)/ 19) 1/2 We apply Lemma 3.2 to the residual problem (V 1o, of), e, B -(o))).
6: return arg wugmaxxeequee augmaxxeq.dd))afff33
As a result, POMC returns a solution Xo, satisfying Xo, S
B- -(oy) and f(Xo, 1r) 2 (1 (1-z(r)) S(X* 0g).
form new candidate solution set = (X,.U Vu E V) (line 4). Finally, EPOL returns the best feasible solution among these candidate solutions (line 6). The idea of EPOL is inspired by (Feldman et al., 2023).
Rearranging this inequality yields
S(Xo; Uof) 2 (1 - (())) (f(x*) - [(o))) + f(or)
flor)
2 (1- - 2( ((x)) (f(x*) - flor)) + f(or),
In Theorem 4.1, we prove that EPOL can achieve an ap- proximation ratio of 0.6174 using at most en PPaaa / expected number of iterations. The key to the proof is estab- lishing connection between the approximation guarantees of the residual problem (V\of, of, J( of).e, B - -c((o)) and the original problem, primarily by using Lemma 3.2, where Of E arg max f(v).
where the second inequality holds by Eq. (11) and the non- decreasing property of z(-). Let = f(o))/(((( where
E [0, 1/3]. Then, the above equation becomes f(Xo, U of) 2 ((1 - =)=-))) (1 1) +t) -(x*) 2 0.6174 f(X*), where the second inequality holds by Lemma 13 of (Feldman et al., 2023). The solution Xo, Uoy will be contained in Q in line of Algorithm 2.
Theorem 4.1. For the problem in Definition 2.1, EPOL with at most en² B maz/ 1 expected number of iterations finds a subset X C V such that e(X) S B and
Hence, EPOL guarantees solution X such that c(X) S B and f(X) 2 (2/3,, 0.6174). (6174)-/(X*)
f(X)= Z 0.6174 f(X*).
0.6174 64 ((X*). As EPOL runs POMC n times for solving the n residual problems, the total expected number of iterations is at most n en Pmnnn/b Thus, the theorem holds.
Proof: Let of be the largest-value item in the optimal so- lution X*iie., Of E arg max f(v). We can observe that X" oo is an optimal solution of the residual problem (V) \ oy, f( | oy). B, B -33---0 e(or)). For any X C V of with e(X) S B c(or). it holds that
The processes in lines 2-5 of Algorithm 2 are independent and can run in parallel on N processors. This reduces the expected number of iterations to en² B Praz/ (N8) (Corol- lary 4.2). When N n, the expected number of iterations can reduce to en enBPrnall Pmaa//d 88 as same as that of POMC
f(x* oy of) 2 f(X or). or).
We now prove Theorem 4.1 by considering the relationship between f(or) and f(X*).
Corollary 4.2. For the problem in Definition 2.1, EPOL with at most en BP Pmez/ / expected number of iter- ations finds a subset X C V such that c(X) < B and f(X) 2 0.6174 f(X*), where N denotes the number of processors used by EPOL.
Case 1: Assume that (or) 2 (1/3)-[(X*) Given that the function f is submodular, it can be verified that f( | v) is also submodular. According to Theorem 3.1, for the residual problem (V (or. f(- of), c, B 33-c(or) POMC will return solution X., satisfying that X., I B c(or) and
Note that in our experiments, EPOL executes only on KB residual problems corresponding to the top-Kg items with the highest values, where B denotes the maximum num- ber of items in subset X that satisfies the budget constraint c(X) < B. Notably, K is non-decreasing with respect to the budget B, implying that EPOL will execute more resid- ual problems as the problem becomes harder (i.e., when the budget B increases). Despite this limitation, EPOL still shows superior performance.
f(Xo, /r)) 2 (1/2) f(x* \os oÿ).
By rearranging the above inequality, we obtain
f(x,, Uoy) 2 f(x*)/2+ f(or)/2 2 (2/3) f(x"), where the last inequality is by the assumption f(oy) Z (1/3) - f(x).. The solution Xo, Uo will be contained in Q in line of Algorithm 2.
7

---

Improved TheorrticallyGGrondeee Evolutionary Algorithms for Subset Selection with Linear Cost Constraint
5. Empirical Study
EA-based methods follows:
We empirically examine EPOL on the applications of max- imum coverage and influence maximization, by compar- ing series of competitive algorithms, including greedy algorithms and the EA-basek methods. The source code is available at http::/ggihub.coommmmmabbbbbb
GGA (Zhang & Vorobeychik, 2016): Iteratively selects an item maximizing the ratio of the increment on f and c, and outputs the best solution among the subset X; found by the iterative process and single items, i.e., (Xi) Ue u V3.
5.1. Experimental Settings
Greedy+ (Yaroslavtsev et al., 2020): Extends GGA by outputting the best solution in {X,} U {X, Uv Uv|0s 1 j S i E V c(x, Uv) - B).
Maximum Coverage. Given a set U of items, and a col- lection V= S2, } of subsets of U, maximum coverage (Feige, 1998) is to select a subset of V to maximize the number of covered items of U under a cost budget B, i... arg x Us.ex S.l. The objective func- tion is easily verified to be monotone and submodular. We use three real-world graph datasets: frb30-15-1 (450 ver- tices, 17,827 edges) and frb35-17-1 (595 vertices, 27,856 edges), both studied in (Bian et al., 2020; Roostapour et al., 2022), as well as the Twitter Interaction Network for the US Congress, congress (475 vertices, 13,289 edges) (Fink et al., 2023). For each vertex, we generate a set which contains the vertex itself and its adjacent vertices. The cost of each vertex (set) is c(v)= 1 ++ +mxx(((()) 0} as in (Harshaw al., 2019), where dd()) is the out-degree of and is constant. We set g {0, 5, 10} and the budget B E (300, 350,...,5000, 5003.
1 1-gues--Greddy* (Feldman et al., 2023): Performs a single partial enumeration on Greedy+.
POMC (Qian et al., 2017a): Maximizes f and mini- mizes simultaneously, through multi-objective EA process.
EAMC (Bian et al., 2020): Searches solutions guided by surrogate function of integrating f and c, and maintains a limited number of solutions for each possi- ble subset size.
EVO-SMC (Zhu et al., 2024): Similar to EAMC, but uses different surrogate function of integrating func- tion f and function c.
FPOMC (Bian et al., 2021): Modifies POMC by intro- ducing greedy selection strategy.
Influence Maximization. Given a directed graph G = (V, E) representing a social network, influence maximiza- tion (Kempe et al., 2003) is to find subset of users X S V such that the expected number of users activated by prop- agating from X is maximized, while satisfying the cost constraint, i.e., arg maxxgV is the set of users activated by propagating from the seed users X under the Independence Cascade model. It be- gins with X, uses a set A, to record the nodes activated at time I, and at time t + 1, each inactive neighbor v of E A, becomes active with edge probability Pa,ei this process is repeated until no nodes get activated at some time. The function [x]]](X)]] is monotone and submodu- lar. We use three real-world graph datasets: graph100 (100 vertices, 3,465 edges) and graph200 (200 vertices, 9,950 edges), widely used as social networks in influence maxi- mization (Bian et al., 2020), as well as the animal interaction network insecta (152 vertices, 6,716 edges). The cost of each node is caleulated based on its out-degree d(v), i.c., c(t) = 1 + (1 Igl)- d(u), where & is random number drawn from the normal distribution (0, 0.5²). To calcu- late []]] in our experiments, we simulate the random propagation process starting from the solution X for 500 times independently, and use the average as an estimation. We set the probability of each edge as (0.05, 0.1) and the budget B as {100, 200,..., 5003.
The algorithms in our study fall into two categories: Fixed- time algorithms such as GGA, Greedy and I-guess Greedy+, with runtime complexities of O(KKB), O(nKB), B), and ((²KB)) respectively, and anytime algorithms such as POMC, EAMC, FPOMC, and EVO-SMC, whose perfor- mance improves with runtime. To ensure fair comparison, the number of objective evaluations for POMC, EAMC, FPOMC, and EVO-SMC is set to Kn EPOL divides the original problem into n residual problems (V \ v, f( | v), c, B - c(v) for each v E V. Note that we only run the residual problems corresponding to the top-KB values of (() to balance computational efficiency and performance, rather than all n residual problems. These KB subproblems are then solved by POMC in parallel with 20nK n evalua- tions. The ratios of K 1//n in our experimental settings can be found in Table 4 of Appendix B.2. For all E.Aeaased methods, we independently repeat the run 10 times and report the average results. The objective evaluation for in- fluence maximization, i.e., [X]]C((X]]] is noisy because the propagation process is randomized, and we use the av- erage of multiple Monte Carlo simulations to estimate the expectation. Specifically, starting from solution X, we simulate the propagation 500 times and use the average as the estimated objective value. Since the behavior of greedy algorithms is randomized under noise, we also repeat their
B[]/C(X]]]. IC(X)
Settings. We compare the SOTA greedy algorithms and
8

---

Improved Theoretically-Crondde Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Table The objective value (number of covered vertices) of maximum coverage (avg - std) obtained by the algorithms on frb35-17-1 for = 5 and the budgets B é {300, 350, 500}. For each B, the largest number is bolded, and "e/o" denote that EPOL is significantly better/worse than the corresponding algorithm by the Wilcoxon signed-rank test with confidence level 0.05, Avg.R. denotes the average rank (the smaller, the better) of each algorithm under each setting as in (Demsar, 2006).
Budget
300
350
400
450
500
Avg.R.
GGA (Zhang & Vorobeychik, 2016)
309.0
339.0
368.0
424.0
Greedy+ (Yaroslvisevv al., 2020)
309.0
339.0
368.0
401.0
425.0
4.4
I-guess- Greedy T (Feldman al. 2023)
314.0
352.0
385.0
412.0 e
440.0
2.6
EVO-SMC (Zho et al., 2024)
292.6 6.2
325.8 3.18:15111
355.3
5.7
381.9
410.5 4.4
FPOMC (Bian al., 2021)
303,9 = 4.3
3.9
368.6 1:666::00 4,4
398.1 3.9
423,2 5,4
6.0
EAMC (Bian et al., 2020)
297.1 = 3.2
333.5
5.0
364,1
+ 5.1
398.5 +
425.5 5.7
6.2
POMC (Qian al., 2017a)
314.6 1.8
350,9
383.7
413.8 2.6
4
EPOL (ths puper)
319.1 + 0.8
356.6 1 0.9
389.8 0.6
419.0 + 0.6
446.7 1 0.6
1.0
To further assess the effectiveness of EPOL., we compare it with P-POMC, a variant that solves the original problem KB n times independently using K parallel processors in- stead of KB independent residual problems, where each processor is also allocated budget of 20m evaluations. The best solution among K B processors is selected as the final output for a single run. We run P-POMC 10 times and compare it with EPOL. EPOL consistently achieves better solutions (Table 10, Appendix B.4). Although the setting that EPOL runs a subset of residual problems (KB residual problems) sufficient to show the superiority of the proposed EPOL as the implemented version is weaker, conduct additional experiments comparing EPOL (as in the previous experiments) with the full version (EPOL-full), which enumerates all residual problems. The results of Ta- ble 11 in Appendix B.5 show that EPOL-full consistently outperforms EPOL with significant advantages in several cases, highlighting EPOL-full's 's potential to improve perfor- mance by addressing all residual problems. Figures 2 and in Appendix B.6 illustrate the curves of the average values over runtime, where EPOL surpasses all greedy algorithms within 12nKg and 4nK runtime for maximum coverage and influence maximization, respectively.
Table 3. Average ranks of algorithms on datasets: MC1 (frb30-15- I). MC2 (frb-35-17-I,, MC3 (congress) for maximum coverage with q 5; IMI (graph100), IM2 (graph200), IM3 (insecta) for influence maximization with an edge probability 0.05. The smaller, the better.
MCI
MC2
MC3
IMI
IM2
IM3
GGA
5.4
5.4
6.0
7.8
8.0
8.0
Greedy+
4.0
4.4
5.0
6,4
7.0
6.6
1-guess- +rees++
2.4
2.6
2.2
4.0
5.4
3.6
EVO-SMC
8.0
8.0
7.0
5.6
3.6
4.8
FPOMC
7.0
6.0
8.0
5.4
5.2
5.0
EAMC
5.6
6.2
4.0
3.0
2.2
3.4
POMC
2.6
2.4
2.8
2.8
3.0
3.2
EPOL
1.0
1.0
1.0
1.0
1.6
1.4
run 10 times independently and report the average results for the application of influence maximization.
5.2. Experimental Results
We report the average results of maximum coverage ob- tained by each algorithm on frb35-17-1 with q = 5 in Ta- ble 2. Additional results are provided in Tables to of Appendix B.2 due to space limitation. Across all settings, EPOL remains significantly superior in almost all cases and never significantly outperformed.
6. Conclusion
In this paper, we improve the approximation ratio of POMC to 1/2, providing a clearer theoretical understanding for its promising empirical results. Additionally, we propose EPOL, novel multi-objective EA that achieves the best- known practical approximation guarantee of 0.6174 while demonstrating superior empirical performance. We believe this work can advance solving the subset selection problem but also deepen our theoretical understanding of EAs.
We summarize the average rank on two applications in Ta- ble 3. Among the three greedy methods, GGA performs the worst, while 1-guess-Greede Greedy performs the best. For EA- based methods, EAMC, FPOMC, and EVO-SMC underper- form greedy methods in maximum coverage but can excel in influence maximization, indicating performance instability across tasks. Overall, POMC is the best performer except EPOL, showing small and robust average rank across both applications. EPOL clearly performs the best. We also compare Sto-EVO-SMC (Zhu et al., 2024), a stochastic vari- ant of EVO-SMC, which shows minimal difference across parameter settings and underperforms compared to EPOL (Figure 1, Appendix B.3).
Impact Statement
Subset selection with a linear cost constraint is funda- mental problem in many applications. While EAs have shown competitive empirical performance, they lag behind greedy algorithms in approximation guarantees. This paper

---

Improved Theoretically-Crondeed Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
deepens theoretical understanding of EAs and advances the solving of subset selection. We refine the analysis of the SOTA EA, POMC, improving its approximation guarantee to 1/2, and introduce a novel EA, EPOL, which achieves the best-known practical approximation ratio of 0.6174 and demonstrates superior empirical performance.
Demsar, J. Statistical comparisons of classifiers over multi- ple data sets. Journal of Machine Learning Research, 7: 1-30, 2006.
Ene, A. and Nguyen, H. L. A nearly-linear time algorithm for submodular maximization with a knapsack constraint. Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICAL,P'19, pp. 53:1-53:12, Patras, Greece, 2019.
Acknowledgements
This work supported by the National Science and Tech- nology Major Project (20227D01 16600), the National Sci- ence Foundation of China (62276124), and the Fundamental Research Funds for the Central Universities (14380020).
Feige, U. A threshold of In for approximating cover. Journal of the ACM, +5(4):634-652, 1998.
Feldman, M., Nutov, Z., and Shoham, E. Practical budgeted submodular maximization. Algorithmica, 83(5): 1371, 2023.
References
Ashkan, A., Kveton, B., Berkovsky, S., and Wen, Z. Optimal greedy diversity for recommendation. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15, pp. 1742-1748, Buenos Aires, Argentina, 2015.
Feng, C., Qian, C., and Tang, K. Unsupervised feature selec- tion by Pareto optimization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI' 19), pp. 3534 3541, Honolulu, HI, 2019.
Bäck, T. Evolutionary Algorithms in Theory and Prac- fice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford, UK, 1996.
Fink, C. G., Fullin, K. Gutierrez, G., Omodt, N., Zinnecker, S., Sprint, G., and McCulloch, S. A centrality measure for quantifying spread on weighted, directed networks. Physica A: Statistical Mechanics and its Applications, 626: 12008, 2023.
Badanidiyuru, A. and Vondrák, J. Fast algorithms for maxi- mizing submodular functions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA' 14)) pp. 1497-1514, Portland, Oregon, 2014.
Friedrich, T. and Neumann, Maximizing submodular functions under matroid constraints by evolutionary al- gorithms. Evolutionary Computation, 23(4):543-558, 2015.
Bian, C.,, Feng, C.,, Qian, C., and Yu, Y. An efficient evolu- tionary algorithm for subset selection with general cost constraints. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (A)AI'20), pp. 3267-3274, New York, NY, 2020.
Golovin, D. and Krause, A. Adaptive submodularity: The- ory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-4866 2011.
Bian, C., Qian, C., Neumann, F., and Yu, Y. Fast Pareto optimization for subset selection with dynamic cost constraints. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI21), pp- 2191-2197, Montreal, Canada, 2021.
Harshaw, C., Feldman, M., Ward, J., and Karbasi, A. Sub- modular maximization beyond non-negativity: Guaran- tees, fast algorithms, and applications. In Proceedings of the 36th International Conference on Machine Learn- ing (ICML'19) pp. 2019.
Long Beach, California,
Bian, C., Zhou, Y., and Qian, C. Robust subset selection by greedy and evolutionary Pareto optimization. In Pro- ceedings of the 31st International Joint Conference Vienna,
Kempe, D.,, Kleinberg, J., and Tardos, É. Maximizing the spread of influence through social network. In Proceed- ings of the 9th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD '03), pp. 137-146, Washington, DC, 2003.
Artificial Intelligence (IJCA'222, pp- Austria, 2022.
De. A., Koley, P., Ganguly, N., and Gomez-Rodriguez, M. Regression under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 20), volume 34, pp. 2611 122200 2020.
Krause, A. and Guestrin, C. A note on the budgeted max- imization on submodular functions. Technical Report CMU-CALD-05-1 103, Carnegie Mellon University, 2005.
10

---

Improved Theoretically-Crondeed Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Krause, A., Guestrin, C., Gupta, A., and Kleinberg, M. Near-optimal sensor placements: Maximizing informa- tion while minimizing communication cost. In Proceed- ings of the 5th International Conference on Informa- tion Processing in Sensor Networks (IPSN (6)), pp. 2-10, Nashville, TN, 2006.
Qian, C. Multiobjective evolutionary algorithms are still good: Maximizing monotone approximately submodular minus modular functions. Evolutionary Computation, 29 (4):463-45)) 0903-499,200 2021.
Qian, C., Yu, Y., and Zhou, Z. Subset selection by Pareto optimization. In Advances in Neural Information Pro- cessing Systems 28 (NIPS' 15), pp. 1774-1782, Montreal, Canada, 2015a.
Kulik, A., Schwartz, R., and Shachmai, H. A refined analysis of submodular greedy. Operations Research Letters, 49 (4):507-514, 2021.
Qian, C., Yu, Y., and Zhou, Z. Subset selection by Pareto optimization. In Advances in Neural Information Process- ing Systems 28 (NeurIPS' 15), pp. 1765-1773, Montreal, Canada, 2015b.
Laumanns, M., Thiele, I.., and Zitzler, E. Running time anal- ysis of multiobjecttiv evolutionary algorithms on pseudo- Boolean functions. IEEE Transactions on Evolutionary Computation, 8(2):100-822, 2004.
Qian, C., Shi, J., Yu, Y., Tang, K., and Zhou, Z. Parallel Pareto optimization for subset selection. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (U), pp. 1939-1945, New York, NY, 2016.
Li, W., Feldman, M., Kazemi, E., and Karbasi, A. Submod- ular maximization in clean linear time. In Advances in Neural Information Processing Systems 35 (NeurlPS' 22), New Orleans, LA, 2022.
Lin, H. and Bilmes, J. Multi-document summarization via budgeted maximization of submodular functions. In Proceedings of the I 11th Annual Conference of the North American Chapter of the Association for Computational Linguistics (VAACL'O)) pp. 912-920, Los Angeles, CA, 2010.
Qian, C., Shi, J., Yu. Y., and Tang. K. On subset selection with general cost constraints. In Proceedings of the 26th International Joint Conference Artificial Intelligence (IJCAI' 17), pp. 2613-2619, Melbourne, Australia, 2017a.
Qian, C., Shi, J., Yu, Y., Tang, K., and Zhou, Z. Optimizing ratio of monotone set functions. In Proceedings of the 26th International Joint Conference on Artificial Intelli- gence (IJCA''17, pp. 2606-2612, Melbourne, Australia, 2017b.
Liu, D. and Qian, C. Biased Pareto optimization for subset selection with dynamic cost constraints. In Proceedings of the 18th International Conference on Parallel Problem Solving from Nature (P), pp. 236-251, Hagenberg, Austria, 2024.
Qian, C., Shi, J., Yu, Y., Tang, K., and Zhou, Z. Subset selection under noise. In Advances in Neural Information Prucessing Systems 30 (NIPS' 17), pp. 3560-3570, Long Beach, 2017c
Liu, D., Mu. X., and Qian, C. Human assisted learning by evolutionary multi-objective optimization. In Proceed- ings of the 37th AAAI Conference on Artificial Intelli- gence (AAAI'23), pp. 12453-12461, Washington, DC, 2023.
Qian, C., Shi, J.-C., Tang, K., and Zhou, Z.-H. Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Transactions on Evolutionary Computa- tion, 22(4):595-600 2017d.
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14(1): 265-294, 1978.
Qian, C., Zhang, Y., Tang, K., and Yao, X. On multiset selection with size constraints. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI'18), pp. 1395-1402, New Orleans, LA, 2018.
Neumann, F. and Rudolph, G. Archive- single- objective evolutionary algorithms for submodular opti- mization. Proceedings of the 18th International Confer- ence on Parallel Problem from Nature (PPSN'24), pp. 166-180, Hagenberg, Austria, 2024.
Qian, C., Yu, Y., Tang, K., Yao, X., and Zhou, Z. Maximiz- ing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms. Ar- tificial Intelligence, 275:279-294 2019.
Neumann, F. and Witt, C. Fast Pareto optimization using sliding window selection. In Proceedings of the 26th Eu- ropean Conference on Artificial Intelligence (ECAI'23), pp. 1771-1778, Kraków, Poland, 2023.
Qian, C., Bian, C., and Feng, C. Subset selection by Pareto optimization with recombination. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (0), pp. 2408-22 -415,, New York, NY, 2020.
Qian, C. Distributed Pareto optimization for large-scale noisy subset selection. IEEE Transactions on Evolution- ary Computation, 2444):694-707, 2020.

---

Improved Theoretically-Crondeed Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Qian, C., Liu, D.-X., and Zhou, Z.-H. Result diversification by multi-objective evolutionary algorithms with theoreti- cal guarantees. Artificial Intelligence, 309:103737, 2022.
Qian, C., Liu, D.-.., Feng. C., and Tang. K. Multi-objective evolutionary algorithms are generally good: Maximizing monotone submodular functions over sequences. Theo- retical Computer Science, 943:241-266, 2023.
Roostapour, V., Neumann, A., Neumann, F., and Friedrich, T. Pareto optimization for subset selection with dynamic cost constraints. Artificial Intelligence, 2022.
Sviridenko, M. note on maximizing a submodular set function subject knapsack constraint. Operations Research Letters, 32(1):41-43 2004.
Tang. J., Tang. X., Lim, A., Han, K., Li, C.,, and Yuan, Revisiting modified greedy algorithm for monotone sub- modular maximization with knapsack constraint. SIG- METRICS Performance Evalution Review, 4961)663-6, June 2022.
Yaroslavtsev, G., Zhou, S., and Avdiukhin, D. "bring your own greedy" +max: Near-optimal 1/2 approooxximtsonns for submodular knapsack. In Proceedings of the 23rd Interna- tional Conference Artificial Intelligence and Statistics (AISTATS'200 20), pp. 3263-3274, Sicily, Italy, 2020.
Zhang, H. and Vorobeychik, Y. Submodular optimization with routing constraints. In Proceedings of the 30th Con- ference Artificial Intelligence (AAAI' 16), pp. 819-826, Phoenix, AZ, 2016.
Zhou, Z., Yu, Y., and Qian, C. Evolutionary Learning: Advances in Theories and Algorithms. Springer, 2019.
Zhu, Y., Basu, S., and Pavan, A. Improved evolutionary algo- rithms for submodular maximization with cost constraints. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (JCCAI224, pp. 7082-7090, Jeju, South Korea, 2024.
12

---

Improved Theoretically-Crondeed Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
A. Omitted Proof of Lemma 3.3
Lemma A.l. For any subset X S V such that the total cost c(X) S B c(oo). where Og E arg max c(o), there exists a solution X' X U E² that satisfies
(1 (1-60 a...)... .u")
a. c(0))
_(X') ((x) 2
((Xx))((XUX))
(s(X*) -
B c(oe)
B - B-((0))
where V² E arg max ((XU)(
f(X and E [0,
d()
Proof. By the definition of submodularity, we have
f(X')X - f(x
E
((X - f(X
EE ((XUas)
c(v) 1(XU))- 1(x)
E
E
d())
(12)
(EX-((XUO))
[(XU))))(X) f(X).
d(u B c(oo)), (
E
d(²)
c(o)
(XXua))
where the first inequality holds by Eq. (3), the second inequality holds by Eq. (2), the third inequality holds by the definition of v", and the last inequality holds because the total cost of items in X (X U 0z) does not exceed B c(Oc).
Since f' is monotone, we also have ʃ(X* o.) 2 f(X*). Combining this with Eq. (12), we have
c(l*)
[(X - ((X)) B - d0o) (f(X*) - S((Uoa))
a1-a).c(1)) (f(X') f(X + B - c(o.) (f(X*) f(od) - -(()).
c(u")
- do.)
where E [0, and the second inequality is by the submodularity (i.e., Eq. (2)) of f. that is, f(X U - f(X) < f(oz) - f00) = f(o.).
B. Additional Experimental Results
B.1. Settings
three real-world graph datasets: frb30-15-/ (450 vertices, 17,827 edges), frb35-17-1 (595 vertices, 27,856 edges), and congress (475 vertices, 13,289 edges) (Fink et al., 2023). We set g (0, 10] and the budget B E (300, 350. ..., 500]. For the application of ifluence maximization, we use three real-world graph datasets: graph100 (100 vertices, 3,465 edges), graph200 (200 vertices, 9,950 edges), and insecta (152 vertices, 6,716 500].
For the application of maximum coverage,
edges). We set the probability of each edge as {0.05,0.1 0.1} and the budget B as (100,
We compare EPOL with several competitive algorithms, including SOTA greedy algorithms such as GGA, Greedy+ and 1 I-guess-Greedyee and the EA-based methods such as POMC, EAMC, FPOMC and EVO-SMC. The number of objective evaluations for POMC, EAMC, FPOMC and solve Kg residual problems. We list the ratios of KB/ /n in our experimental settings in Table 4. The number of K used in our experiments is no more than 32% of n.
is set to 20nKg. EPOL runs the process of POMC in parallel to
For all EA-based methods, we independently repeat the run 10 times. Since the behavior of greedy algorithms is randomized under noise, we also repeat their run 10 times independently for the application of influence maximization.
B.2. Additional Results on All Settings
In this section, we report the average results of each algorithm across various settings. Specifically, we detail the average results on maximum coverage with q E 50,5, 10) in Tables 5 to 7, respectively. For the application of influence maximization, we report the average results with a probability of each edge as {0.05, 0.13 in Tables 8 and 9, respectively.
13

---

Improved Theoretically-Cronnde Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Table Ratios of KB/n for different settings in two applications. For maximum coverage, (-).-)) represents KB/ ratios for q = {0, 5, 10). For influence maximization, (.-) indicates KB/n ratios at edge probabilities {0.05, 0.1).
Maximum coverage
300
350
400
450
500
[1630-11-1 vertices, 17,827 edges)
(12%, 16%, 21%)
(12%. 175t 23%)
(13%. 18%, 24%)
(14%. 19%, 25%)
20%s, 26%)
[r625-17-J (595 vertices, 27,8 .56 edges)
(2%, 318)
(3%, 3%, 4%5) (8%, 21%)
(3%, 4%))
(3%, 49% 510
(3%,, 49% 51)
congress (475 vertices, 13,289 edges)
(7%. 12%, 19%)
(9%, 14%. 22%)
(10%, 15%, 23%)
(11%, 16%, 25%)
Indluence maximizaatin
B
100
200
300
400
500
gruph100 (100 vertices, 3,465 edges)
(14%. 14%8)
(20%. 20%)
(25%. 25%)
(29%. 29%)
(32%, 32%))
gruph200 (200 vertiees, 9,950 edges)
(898. 8%))
(12%8. 12%)
(15%.. 15%)
(17%.. 17%)
(19%. 19%8)
insecta (152 vertices, 6,716 edges)
(11%, 11%)
(16%. 16%)
(19%. 19%)
(22%% 22%)
(25%, 25%8)
As expected, the objective value achieved by each algorithm increases with B due to the monotonicity of the objective. Among the three greedy methods, GGA consistently performs the worst, Greedy+ performs slightly better than GGA, and 1 gguess-Greddy" performs best, occasionally surpassing EA methods. The performance order of these greedy methods is reasonable because Greedy+ is an extension of GGA, and "guees-Greedy" is further enhanced by performing a single partial enumeration on Greedy*. Therefore, the solutions found by Greedy* contain those of GGA, and the solutions found by 1-guess-Greeddy+ contain those of Greedy+. This relationship explains the progressive improvement in performance.
For EA-based methods, EAMC, FPOMC, and EVO-SMC generally perform worse than greedy methods in most cases when it comes maximum coverage. However, they tend to excel in influence maximization, as shown by their lower average rank in this task. This suggests that their performance is inconsistent and varies significantly across different tasks. Overall, POMC stands out as the most reliable and well-rounded performer among all existing algorithms, maintaining lower average ranks across various settings in both applications. It performs on par with "reeedy--redy"" in maximum coverage, as their average ranks are closely matched, while in influence maximization, POMC achieves a better overall ranking than other EA-based methods. Across all settings, EPOL significantly outperforms other algorithms in nearly all cases, as confirmed by the Wilcoxon signed-rank test (Demsar, 2006) at a 0.05 confidence level. Exceptions are observed in specific cases involving POMC and gguess-Greedy on maximum coverage, as well as EAMC and EVO-SMC on influence maximization, under certain combinations of the budget B. However, EPOL is never significantly outperformed in any scenario.
Table 5. The objective value (number of covered vertices) of maximum coverage (avg + std) obtained by the algorithms when 0 and the budgets E (300, 350, ., ..00).. For each B, the largest numher is bolded, and "e/o' denote that EPOL. is significantly better/worse than the corresponding algorithm by the Wilcoxon signed-rank test with confidence level 0.05. Avg.R. R. denotes the average rank (the smaller, the better) of each algorithm under each setting as in (Demsar, 2006).
fr030-15-/ vertices, 17,827 edges)
Budget B
300
350
400
450
500
Avg.R.
GGA (Zhang & Vorbheychik, 2016)
260.0 +
291.0
315.0 *
346.0
358.0
6.0
Gready ! (Yarodavtsev al., 2020)
260.0
291.0
318.0
346.0
364.0
5.0
I-guess-Greedy+ (Feldman al., 2023)
267.0
298.0
326.0
350.0
367.0
2.6
EVO SMC (Zhu et al., 2024)
259.5 +: 1.9
289.5
1.0
318.1 :: 2.8
334.9 :: 3.1
353.9 1: 2.5
6.8
FPOMC (Bian al., 2021)
254.8
5.2
286.7
-
313.9
336.4 - 7,2
353.7 +
7.8
EAMC (Bian al., 2020)
263.3 =
294.7
3.6
324.7
= 3.2
345.9 = 2.3
365.0
+ 2.9
4.4
POMC (Qian et al., 201 7a)
267.2
300.2 1.3
325.6
2.1
349.1 # 1.5
369.1 +: 3.1
2.4
EPOL. (this paper)
269.9
0,9
301.4
330.0
0.6
352.9 1. 0.3
373.1
0.9
1.0
fro25-17-1 (595 vertices, 27 856 edges)
GGA 1Zhang & Varobeychii,, 2016)
273.0
312.0 .
346.0
373.0
399.0
6.2
Greedy+ (Yarodavtsev al., 2020)
273.0
312.0
346.0
373.0
400.0
I-guess GGeeddy i (Feldman al., 2023)
283.0
321.0
353.0
386.0
415.0
2.0
EVO-SMC (Zhu al.,, 2024)
276.0 2.1
308.5
3.7
337.6 - 2.7
364.4 = 4.0
391.2 2.4
7.4
FPOMC (Bian al.,
339.8
2.7
369.6
5.3
396.8
7.2
EAMC (Bian el al., 2020)
277.6 1: 2.4
312.9
1. 3.3
347.7
:: 2.0
377.8 1: 3.4
409.2
1:
4.0
POMC (Qian et al., 2017a)
280.3
2.0
317.8
353.1
1.3
382.9
2.5
412.6 + 3.2
2.8
EPOL (this paper)
282.9 1 0.3
321.0
0.0
355.2 + 0.4
388.0 1: 0.9
417.6 0.5
1.2
congress (475 vertioes, 13,289 edges)
GGA (Zhang & Voroheychik,, 2016)
271.0
298.0
320.0
341.0
358.0
6.6
Gready+ (Yaroslavtsev al., 2020)
271.0
298.0
322.0
341.0
358.0
5.6
guess Greedyy + (Feldman al., 2023)
282.0
304.0
331.0
355.0
372.0
4.0
EVO-SMC (Zhu et al., 2024)
274.9
7.4
305.9
6.8
324.7 774
339.3 - 3.5
351.3 4.9
5.6
FPOMC (Bian al., 2021)
248.1
275.9=1.6
299.3 -
319.7 8.6
337.4$4.55
8.0
EAMC (Bian et al., 2020)
277.0 1: 4.3
307.6 =
332.0
- 7.8
358.7 - 1.0
372.4
1:44::20 2.2
3.2
POMC (Qian al.,
282.7
316.2
339.7
359.4
376.4 1
2.0
EPOI. (his paper)
283.0 1: 0.0
317.0 + 0.0
341.0 - 0.0
360.9 - 0.3
378.0 1: 0.0
1.0
14

---

Improved Theoretically-Cromdded Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Table The objective value (number of covered vertices) of maximum coverage (avg + std) obtained by the algorithms when = 5 and the budgets B (300, ...,...,, 500). For each B, the largest number is bolded, and "o/o" denote that EPOL is significantly better/worse than the corresponding algorithm by the Wilcoxon signed-rank test with confidence level 0.05. Avg. denotes the average rank (the smaller, the better) of each algorithm under each setting as in (Demsar, 2006).
frb30-13-7 (450 vertices, 17,827 edges)
Budget B
300
350
100
450
500
Avg.R.
(7hang Voroheychik, 2016)
358.0
Groody (Yaroslavtsev 2020)
292.0
322.0
344.0
361.0
377.0
4.0
1-gues-GGreddy" (Feldman al., 2023)
297.0
324.0
346.0
370.0
386.0
2.4
EVO-SMC (2hu al., 2024)
274.9
305.6
3.9
330.8 #:
347.5 = 5.0
365.0
8.0
FPOMC (Bian 2021)
283.2
332.6
356.2
4.2
7.0
EAMC (Bian et al., 2020)
288.9
3.5
320.7 + 4,0
340.3 +
358.8 = 4.9
375.2 3.5
5.6
(Qia
348.4
369.2
EPOI. (this paper)
301.1 + 1.0
329.7 + 0.5
354.4 + 0.9
375.2 + 1.5
394.1 +: 1.8
1.0
fr635-17-1
(595 vertices, 27,835 edges)
(Zhang Vorobeychik, 2016)
309.0
339.0
368.0
401.0
424.0
5.4
Greedy" (Yaroslavtsev 2020)
309.0
339.0
368.0
401.0
425.0
4.4
I-guess- Greedy (Feldman et 2023)
314.0
352.0
385.0
412.0
440.0
2.6
EVO-SMC (2hu sl., 2024)
292.6
325.8 - 5.1
355.3
5.7
381.9
6.0
410.5
8.0
FPOMC (Bian
2021)
303.9
4.3
336.1
+:
368.6 1:
398.1
423.2 5.4
6.0
EAMC (Bian et al., 2020)
297.
331.5
5.0
364.1 1:
398.5
425.5
6.2
POMC (Qian 2017a)
314.6
350.9
2.4
383.7 = 2.6
413.8
2.6
441.5 +
2.4
EPOL (this paper)
319.1 0.8
356.6 J. 0.9
389.8 1: 0.6
419.0
0.6
445.7 :1 0.6
1.0
congress (475 vertices, 13,289 edges)
(Zhang Vorobeychik, 2016)
326.0
348.0
368.0
384.0
6.0
Groody+ (Yaroslavtsev 2020)
326.0
348.0
368.0
384.0
399.0
5.0
L-guess- I-gues-GGredd"" (Feldman et al., 2023)
330.0
355.0
376.0
394.0
410.0
2.2
EVO-SMC (Zhu al., 2024)
309.3 3.6
327.8
3.6
348.3
361.9 =
376.5
7.0
FPOMC (Bian
2021)
295.6 9.3
320.1 +
340.3
353.9 10.3
374.1 4: 12.1
8.0
EAMC (Bian et al., 2020)
327.4
2.5
350.5
1: 2.0
369.5 1.4
385.2 1: 1.9
400.9 2.0
4.0
POMC (Qian 2017a)
329.4
351.9
1.1
375.7 2.1
396.0 3.2
409.2
: 3,3
2.8
EPOL (this papor)
3328
+ 0.4
358.0 + 0.6
381.2
399.9 = 0.7
415.5 - 0.5
1.0
Table The objective value (number of covered vertices) of maximum coverage (avg + std) obtained by the algorithms when q = 10 and the budgets B (300, 350, .., 500)- For each B, the largest number is bolded, and 'o/o" denote that EPOL is significantly better/worse than the corresponding algorithm by the Wilcoxon signed-rank test with confidence level 0.05. Avg.R. denotes the average rank (the smaller, the better) of each algorithm under each setting.
frh33-115/7 (450 vertices, 17,827 edges)
Budget
300
350
400
450
500
Avg.R.
GGA (Zhany Vorobeychik,, 2016)
Greedy" i (Yanoslavtee
2020)
331.0
352.0
372.0
388.0
406.0
4.0
I-guess-Greesd (Peldman al., 2023)
334.0
357.0
375.0
392.0
409.0
3.0
EVO-SMC (Zha et al., 2024)
301
a,9
323.4
346.2 4.3
364.7 ::
381.6
FPOMC (Bian
2021)
322.8
346.8
369.0 -.
386.
3.2
402.6 3.5
6.2
EAMC (Bian et al., 2020)
324.4 + 2,5
345.2
3.5
365.
3.3
379.8
2.0
391.7 :
6.8
(Qian 2017a)
377.3
409.5
EPOL (this puper)
337.2 1.0
362.0
1.2
382.8 1. 0.7
401.3 0.8
415.2 1. 0.9
1.0
(r925-17-1
(595 vertices, 27.856 edges)
GGA (Zhang & Vorobeychik,
342.0
377.0
405.0
433.0
461.0
5.0
Greedy" + (Yanoslavtsev
2020)
344.0
377.0
406.0
433.0
461.0
4.0
iiguess. Gready! (Peldman et 2023)
359.0
392.0
420.0
446.0
471.0
2.4
EVO-SMC (Zha et al., 2024)
321.2 6.2
351.2
373.4
428.4
FPOMC (Bian al., 2021)
341. +,17:2255
371.6 1116=:23
404.5 =
429.1
5.11
455.9 3.8
6.4
EAMC (Bian al., 2020)
334.3 1: 2.6
370.9
4.1
401.6
4.3
432.5
456.9
6.6
POMC (Qian al., 2017a)
354.3
390.4
2.8
419.3
2.0
447.1
474.1
2.6
EPOL (this puper)
359.0 1 0.0
395.9 1: 0.3
425.9 + 0.7
454.0
0.8
477.7 1: 0.6
1.0
comgress (475 vertices, 13,289 edges)
GGA (Zhang & Vorobeychik, 2016)
420.0
432.0
442.0
450.0
457.0
5.0
Greedy + (Yaroslvttsev et al,, 2020)
420.0
432.0
442.0
450,0
457.0
4.0
1 guess. Greedy+ (Feldman et 2023)
423.0
437.0
446.0
453.0
460.0
2.6
EVO-SMC et al., 2024)
386.0 4.5
409.3 4.4
421.5
FPOMC (Bian et al., 2021)
358.7 + 10.5
381.3 = 6.1
393.4 9.00
403.0
11.3
419.7
8.0
EAMC (Bian al., 2020)
414.7 +: 1.1
428.4
-
439.2
447.0
453.2
6.0
POMC (Qian el 2017a)
422.9 1 0.8
436.9
446.8
1.7
455.0
460.2 1 0.9
2.4
EPOL. (this paper)
423.5 4 0.5
0.5 437.1
447.8 - 0.7
455.7 0.5
462.1 1 0.7
1.0
15

---

Improved Theoretically-Croudde Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
Table The objective value (influence spread) of influence maximization (avg + std) obtained by the algorithms for the probability of each edge 0.05 and the budgets B E {100, 200,.... ...., 5.0). For each B, the largest number is bolded, and "o/o" denote that EPOL significantly better/worse than the corresponding al algorithm by the Wilcoxon signed-rank test with confidence level 0.05. Avg.R. denotes
the average rank (the smaller, the better) of each algorithm under each setting.
kniph700 vertices 3,465 edges)
Budget B
100
200
300
100
500
Avg.R.
GGA (Zhang Vorobeychik, 2016)
1.21
0.99
7.8
Greedy+ (Yarsslavtsev al., 2020)
23.87 0.37
35.61
44.22
0.63
50.92 0.61
55.80
6.4
1-gues--Greddy" (Feldman al. 2023)
24.66 0.17
37.17
0.29
45.70 0.33
51.89 0.18
56.91 + 0.26
4.0
EVO-SMC (Zhu et al., 2024)
25.03 0.32
37.39
0.55
44.72 0.79
50.45 = 0.92
54.44 1.02
5.6
FPOMC
al.,
24.29
0.64
36.58
1.12
45.18 0.95
51.24
55.74
5.4
EAMC (Bian et al., 2020)
25.08 +: 0.27
37,80
0.18
45.88 0.44
$1.19 = 0.56
56.21 + 0.34
3.0
POMC (Qian al., 2017a)
0.30
$2.24
2.8
EPOL. (hhis paper)
25.48
0.17
37.98 +: 0.17
46.41
0.24
$2.76 + 0.14
$7.71 = 0.17
1.0
gruph200 (200 vertices, 9,950 edges)
GGA (Zhang& Vorobeychik, 2016)
44.31
70.87
2.55
2.64
109.07
3.16
8.0
Gready+ + (Yanslavtsev al., 2020)
45.12 0.47
81.57 0.72
94.06 0.91
10695 + 1.01
115.22
1.88
7.0
I-guest-Greedy! (Feldman et 2023)
46.11
0.52 0.52
82.56 + 0.75
96.58 0.69
108.97 0.33
5,4
EVO-SMC (Zhu et al., 2024)
48.04 0.44
84.38 0.21
96.81
0.60
109.09 1.66
116.77 1.78
3.6
FPOMC (Bian al., 2021)
46.72 0.77
82,62 2.57
95.92 0.67
108.54
0,90
117.64
0.91
5.2
EAMC (Bian et al., 2020)
47,92 0.43
84.78 0.44
97.06
0.46
0:27 110.81
118.37
2.06
2.2
POMC (Qian al., 2017a)
46.78 0.61
83.87 0.66
98.41
0.59
110.05
119.40
0.24
3.0
EPOL (this puper)
47.79 0.33
84.76 1. 0.35
99.73 1. 0.26
111.04 0.43
120.12 1. 0.26
1.6
insecta (152 vertsces, 6.716 edges)
GGA 1Zhang & Vorobeychik, 2016)
38.09
53.35 4.24
05.48 3.31
75.35
83.17 =
8.0
Greedy+ (Yaroslavtsev al., 2020)
39.49 + 1.07
57.94 + 0.52
68.86 2.65
78.39 = 1.31
84.69 + 1.04
6.6
I-guess- Greeddy + (Feldman et al., 2023)
40.57 0.64
$8.99 + 0.27
72.90 U.66
80.24 = 0.39
86.59 + 0.26
3.6
EVO-SMC (Zha et al., 2024)
41.76 0.28
59.63 0.29
68.73 + 0.87
78.14
85.11 + 0.62
5.0
FPOMC (Bian al., 2021)
40.48 0.57
58.75 0.39
71.70 + 1.82
79.75 = 0.41
85,92 - 0.89
5.0
EAMC (Bian al., 2020)
41.79 :: 0.18
59.66 1: 0.35
70.81
1.18
80.04 1 0.68
86.48 1 0.41
3.2
POMC (Qian al., 2017a)
40.90 1: 0.51
58.40 0.57
73.96
0.40
81.10 0.42
87.15 1 0.28
3.2
EPOL (this papor)
41.64 = 0.26
59.89 + 0.33
74.60
0.20
81.77 = 0.15
88.00 = 0.07
14
Table The objective value (influence spread) of influence maximization (avg + std) obtained by the algorithms for the probability of each edge 0.1 and the budgets B E {100, 200,..., ... 5003. For each B, the largest number is bolded, and "a/o" denote that EPOL significantly better/worse than the corresponding algorithm by the Wilcoxon signed-rank test with confidence level 0.05. Avg.R. denotes the average rank (the smaller, the better) of each algorithm under each setting.
gnaph100 (100 vertices, 3,465 edges)
Budget B
300
350
400
450
500
Avg.R.
(Zhang& Vorobeychik, 2016)
Greedy (Yaroslatssev 2020)
58.28 0.38
68.71
0.97
75.42
0.63
79.47
0.58
82.62 0.42
6.8
-ggness-rredyy ! (Feldman et al., 2023)
59.66 0.26
0.26
71.49 + 0.25
76.79
0.22
80.33
0.17
83.36 0.19
3.6
EVO-SMC (Zha al., 2024)
60.22 0.41
70.34 = 1.26
1.01 15.29
79.81
0.28
82.53 - 0.56
5.8
FPOMC (Bian
2021)
59.05
70.44 1.16
76.40:00.4
80.20
0.62
83.07 0.43
4.8
EAMC (Bian ot al., 2020)
60.40 0.35
71.02 0.74
75.93
0.90
80.07 = 0.41
83.79 + 0.37
3.8
(Qian 2017a)
76.92
0.16
EPOL (this paper)
60.65 1 0.18
72.13 1. 0.12
77.28 1. 0.06
81.37 1: 0.09
84.09 1. 0.05
1.0
gruph200 (200 vertices.
9,950 edges)
(Zhang Vorobeychuk, 2016)
115.79 0099-093
148.37
3.00
159.45
1.22
166.47
168.66 = 1.58
8.0
Greedy (Yaroslavtsev 2020)
116.14 1.35
153.05
0.76
162.60 0.64
169.17
0.88
172.00
1.10
7.0
greest-Greddy (Feldman et al., 2023)
118.53 0 0.47
154.32 + 0.57
163.57 + 0.17
170.43 0.211
173.7
+ 0.45
5.4
EVO-SMC (Zhu al., 2024)
120.36 0.30
155.23 0.12
163.78
169.63 0.89
172.37
1.35
4.6
FPOMC (Bian
2021)
119.88 0.35
155.26
0.17
163.82 0.26
170.70 - 0.35
174.39
0.57
3.4
EAMC (Bian el 2020)
120.66 0.45
155.32 1: 0.18
163.93 1 0.22
170.79 1: 0.45
174.36
0.75
2.2
POMC (Qian al., 2017a)
119.65 0.25
154.91 0.20
163.54 0.18
170.70 -1 0.35
174.72
0.07
4.2
EPOL (this paper)
120.61 + 0.19
155.55 +: 0.28
164.15
0.29
171.14 + 0.09
174.99
0.09
1.2
Insecta (152 vertices, 6,716 edges)
GGA (Zhang& Voroheychik, 2016)
95.34 1.07
107.39 2.65
115.54
1.53
122.04 1.04
126.28 1.000
8.0
Greedy" (Yaroslavisev et al., 2020)
95.85 0.83
111.41 = 0.96
120.15
1.75
124.18 + 0.44
128.16 0.40
6.6
guess Greedy+ + (Feldman et al., 2023)
97.94 1 0.34
113.09 1. 0.38
121.65 1. 0.25
125.13 1. 0.31
129.05 1 0.18
4.8
EVO-SMC (Zha al., 2024)
0.36
113.54 0.56
124.55
128.02
FPOMC (Bian et al. 2021)
98.83 + 0.29
112.95 - 0.52
122.11 1 0.13
125.50 + 0.47
129.33
0.27
4.0
EAMC (Bian et al., 2020)
99.28 1: 0.31
113.93 0.18
120.58
126.21
0.53
128.80
0.22
3.6
POMC (Qian al., 2017a)
98.84
0.31
113.85
0.33
122.06
0.21
126.43
1. 0.20
129.52
0.13
2.8
EPOL (thss paper)
99.52 1: 0.18
114.25 - 0.15
122.38 - 0.11
126.69 1 0.08
129.71
0.09
1.0
16

---

Improved Theoretically-Cromdeed Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
B.3. Results of Sto-EVO-SMC
Sto-EVO-SMC is stochastie version of EVO-SMC, which brings two parameters and p, maintaining the same guarantee EVO-SMC with probability
We rum sto-EVO-SME by setting E {0.1, 0.2, 0.5) and p E {0.2, 0.5), and plot the average results of tto-EVO-SM--epp EVO-SMC and EPOL in Figure 1. We find that all the class of EVO-SMC algorithms (i.e., EVO-SMC and sto-EVO-SMC-cpp shows minimal difference across parameter settings, and performs worse than EPOL in all cases, expect for B = 100 on graph200 and insecia.
Vambee covered vertiees
000
620
502
000
400
640
2- 6P0
40470-0020 142
340
300
-42
PXI
120
RVD
280
302
RVD AMC 5:-03
250
200
200
40C
320
360
403
116
682
Bulget
Budget
Budget
(a) (a)3rr33-114
(b).frb3-11511
(c) congress
132
16 loTuueee 3ghour
70-
LiEuence
Mi-ee and 6.
EXL
Bhddge
Budget
Stafige
(e) graph100
(d) graph200
(f) insecta
Figure 1. average objective values sto-EVO-SMC-ep. EVO-SMC, and EPOL:: number of covered vertices (top) for maximum coverage with g 5 and influence spread (bottom) for influence maximization with the probability of each edge 0.05, where (0.1,0.2,0.5) 0.5) and p 0.5..
B.4. Results of P-POMC
Table 10. The objective value (avg = std) obtained by EPOL and P-POMC for = 5 on maximum coverage and the probability of each edge 0.05 on influence maximization. For each B, the largest number is bolded, and 'e/o" denote that EPOL is significantly better/worse than the corresponding algorithm by the Wilcoxon signed-rank test with confidence level 0.05.
Jrb30-15-7
odgos)
300
350
400
450
500
P.POMC
375.0
EPOL 301.1 1.0
329.7 0.5
354.4 + 0.9
375.2 = 1.5
394,1 188
frh35 (595 vertices, 27.856 edges)
Maximum coverage
FROMC
3.3.1
155.0 0.4
389.5 1
418.2
445.6
EPOL
319.1 0.8
386.6 0.9
389,8 0.6
419.0 = 0.6
445.7 = 0.6
congress
13,289 edgas)
FRMM
330.3 1 U.S.
355.6 U.S
380.0 1.3
399.0 1.0
414.6 1 0.8
332.8
graph700 (100 vertices 3,465 odges)
100
200
300
100
500
P.POMC 0.14
52.75
EPOL.
25.48 1 0.17
37.98
0.17
46.41 0.24
52.76 1: 0.14
57.71 1: 0.17
Influence maximization
20aphZ0 verices, 9,950 edges)
P-POMC
4.34
84.39 = 0.32
99.53 = 0.21
110.88 = 0.17
120.02 = 0.29
EPOL
47.79 = 0.33
84.76 + 0.35
99.73 = 0.26
111.04
0.43
120.12
0.26
6,716 edges)
P-POMC
41.59 - 0.31
39.67 + 0,39
74.47 = 0.24
81.75 + 0.17
87.94 1: 0.24
To evaluate the effectiveness of EPOL, we compare it with a variant called P-POMC. P-POMC, the original problem runs Ka parallel processors instead of solving KB independent residual problems. The best feasible solution among
17

---

Improved TheoreticallyGGrondde Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
these KB processors is used the final output of single P-POMC run. By running P-POMC 10 times and comparing the average results with EPOL,, observe that EPOL consistently outperforms P-POMC. Moreover, EPOL demonstrates significant advantage over P-POMC in certain cases, marked in Table 10. This comparison underscores the effectiveness of EPOL across various scenarios.
B.5. Results of EPOL-full
Although the setting that EPOL runs a subset of residual problems (Kg residual problems) is sufficient to show the superiority of the proposed EPOL as the implemented version is weaker, we conduct additional experiments comparing EPOL (as in the previous experiments) and the full version (EPOL-fulI), which enumerates all residual problems. For 5, the objective values (avg = std) on maximum coverage for three datasets are summarized in Table 11. The results show that EPOL-full consistently outperforms EPOL with significant advantages in several cases, highlighting EPOL-full's potential improve performance by addressing all residual problems.
Table 11. The objective value (number of covered vertices) of maximum coverage (avg + std) obtained by EPOL and EPOL-full when 5 and the budgets B E {300, 3500,.50..... .... 500}- For each B, the larger number is bolded, and 'o/o' denote that EPOL-full significantly outperforms EPOL by the Wilcoxon signed-rank test with confidence level 0.05.
frb. 30.3 15.1 (450 vertices, 17,827 edges)
Budget
300
350
400
450
500
EPOL
L.
329.7 E 0.5
354.4
394.1
EPl
302,1
0.8
330.9 1. 0.3
354.8 1. 0.4
377.3 1.3
395.2 1. 1.1
Jrb-35-17-1 (595 vertices, 27,856 edges)
EPOL
319.1 = 0.8
356.6 = 0.9
389.8 = 0.6
419.0
445.7 0.6
EPOL-tulI
319.8 = 0.4
357.9 + 0,3
390.6 + 0.5
419.0 + 0.0
446.5 + 0.5
congress (475 vertices, 13,289 edges)
EPOL
332.8 0.4
358.0 = 0.6
381.2 =
1099:000 400.2 1.0
413.5 115.5:00..
EPOL-full
333,4 = 0.5
359.0 = 0.6
3814 1 0.7
416.1 + 0.5
B.6. Objective Values vs. Runtime
The class of greedy algorithms, including GGA, Greedy+, and I-guess Greedy+, is composed of fixed-time algorithms with a runtime complexity of O(nKB). On)KB) and O(n²KB), respectively. In contrast, other algorithms are anytime algorithms, whose performance improves with increased runtime. EPOL surpasses all greedy algorithms within 12n for maximum coverage and 4nK'B for influence maximization, shown in Figures and 3. Moreover, EPOL eventually converges to the best objective value in almost all cases.
18

---

Improved Theoretically-Cromdeed Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
200
Numbor covered werlics
200
230
1.20
200
230
6C4
Eguase Grewdy
Number
100
PRDIC
240
30
34
30
20
12
18
352
365
100
130
Numbber covvrred
209
260
Equas
013
EXOUNC
280
280
203
Fire
Dustiim
24
26
10
Number of covvree vertioons
270
320
covereud
1.40
228
330
000
100 INC
Brossic
200
800
Raac
200
Bustine to m5a
Buxtine 15. PRS
Buttino (95)
Wimbbrr CONDE oo 00000005
600
400
800
300
300
300
323
310
CRI
Polc
20
Bustino m/
Nummbo of novered vertirie
300
420
1.2
12
24
Runtime mKg
Figure The average objective value (number of covered vertices) vs. runtime (i.e., number of objective evaluations) for maximum coverage with q and budget B E {300, 350, 400, 450, 500) (from top to bottom) datasets frb-30-15-1 frb35---- (middle). and congress (right). Error bars show standard deviations.
19

---

Improved Theoretically-Crondeed Evolutionary Algorithms for Subset Sclection with Linear Cost Constraint
45.2
400
U'O
End
350
LANG
300
Runtine
io
Rentinz
30-
30.0
275
Inthucttc
Intuenne
23.0
Indlueare
13
015
role:
15.0
10
Dantiise 1K3
Runtane P6
75.0
07.3
72.5
66.
02.5
Infowetre
Infucncc
Iafluracc
$5.0
$75
10
24
10
20
$1.0
10
Runtimel 07'
MKC
110
225
230
Lounsdrese
20
10w0
40
Santine 05'
Rualizze DK's
075
Incureace gpreed
InFoamnn sproad
[nff Cerorr sgroad
725
1.4
34
30
32
36
Ruzzime I0 m555
Figure 3. The average objective value (influence spread) runtime (i.e., number of objective evaluations) for influence maximization with the probability of cach edge 0.05 and budget B {100, 200, 300, 400, 500} (from top to bottom) on datasets graph100 (left), graph200 (middle), and insecta (right). Error bars show standard deviations.
20


Reviews:
[{"review_id": "0Ze7ObCpkL", "reviewer": "Reviewer_b7Tq", "summary": "This paper addresses monotone submodular maximization under a linear cost constraint using evolutionary algorithms. It reanalyzes the Pareto Optimization Algorithm for Monotone Cost functions (POMC), providing an improved approximation ratio of $1/2$. Additionally, the authors propose a novel multi-objective evolutionary algorithm, EPOL, which achieves the best-known practical approximation ratio of $0.6174$. Empirical evaluations on maximum coverage and influence maximization tasks demonstrate the superior performance of EPOL compared to existing methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We greatly appreciate your time and thoughtful feedback. Below are our detailed responses.\n\n---\n\n> The core idea behind improving the approximation ratio of POMC should be introduced at a high level at the beginning of Section 3 ... \n\n> Moreover, the algorithm sections consist primarily of lengthy proofs without sufficient discussion of the high-level ideas...\n\nThank you for your suggestion. In the original paper, we included a high-level explanation of the core idea behind improving POMC's approximation ratio following the proof of Theorem 3.1 (Page 5, left column, lines 307–316). Previous analysis of POMC used a coarse-grained manner to evaluate the lower bound for improving $f(X)$. This led to POMC being able to derive a solution that satisfies $f(X_1) \\geq (1 - 1/e)\\cdot f(X^*)$, which is, however, infeasible, i.e., $c(X_1) > B$. A connection was then established between $X_1$ and two feasible solutions $X$ and $Y$, demonstrating that $\\max\\\\{f(X), f(Y)\\\\} \\geq f(X_1)/2 \\geq (1/2)(1 - 1/e)\\cdot f(X^*)$. This weakens the tightness of the bound. In contrast, our analysis adopts a fine-grained approach to evaluate the lower bound for improving $f(X)$ (the analysis in Lemma 3.3 and the careful design of $J_{max}$ in Lemma 3.2), showing that POMC can find a feasible solution $X_2$ with $f(X_2) \\geq (1/2) \\cdot f(X^*)$ and $c(X_2) \\in (B - c(o_c), B]$. Thanks to your suggestion, we will move this discussion to the beginning of Section 3, which will provide readers with a clearer conceptual overview before delving into technical details. Thank you very much.\n\nTo ensure clarity and readability, we have included brief explanations of each theorem and lemma, along with proof sketches:\n\n- Page 4, left column, lines 198–203: Connection between Theorem 3.1 and Lemma 3.2; Lemma 3.2's role in proving Theorem 4.1.\n- Page 4, left column, lines 211–219: Relationships between Lemma 3.2 and Lemmas 3.3–3.4; their importance in proofs.\n- Page 4, right column, lines 182–189: Core proof idea of Lemma 3.2: Relies on Lemma 3.3 to analyze $J_{max}$ growth and expected iterations.\n\n- Page 5, left column, lines 279–283: Proof sketch for Theorem 3.1.\n- Page 5, left column, lines 307–316: Main idea for improving POMC’s approximation ratio.\n- Page 5, right column, lines 293–299: Proof sketch for Theorem 4.1.\n\nWe believe these explanations provide readers with the necessary intuition to better understand the technical details. Thanks to your suggestion, we will revise to add more intuitive explanations to improve the readability of our work.\n\n---\n\n> However, the technical contribution of the paper appears to be somewhat limited, as the primary advancements rely on modifications and repeated applications of existing methods rather than introducing fundamentally new algorithmic ideas.\n\nThank you for your feedback. We would like to clarify that the proposed EPOL algorithm is not a simple repeated application of existing methods. EPOL decomposes the original problem into multiple residual problems. For each $v\\in V$, it creates a residual problem $(V \\setminus v, f(\\cdot \\mid v), c, B - c(v))$, which is then solved in parallel using POMC. We also compared EPOL with P-POMC (i.e., a simple repetition of POMC, as detailed in Appendix B.4), where POMC directly executes the original problem in parallel, and the best solution is selected as the final output. The experimental results show that EPOL outperforms P-POMC, thereby highlighting the importance of our design over simple repetition.\n\nIn fact, EPOL is carefully designed to analyze the residual problem anchored at the key element $o_f$, defined as $(V \\setminus o_f, f(\\cdot \\mid o_f), c, B - c(o_f))$. It leverages POMC's 1/2-approximation guarantee on the residual problem and connects this guarantee to the original problem, thereby further improving the theoretical bound. Consequently, EPOL not only advances theoretical insights but also attains a SOTA practical performance guarantee.\n\nFrom a practical problem-solving perspective, the primary goal is to design an algorithm that brings measurable performance improvements. We understand and respect the high expectations for fundamentally new algorithmic ideas. While such breakthroughs are exciting, most research focuses on advancing existing methods to achieve measurable improvements. To our understanding, exploring the potential of existing algorithms and further developing them into approaches that yield improvements in both theoretical analysis and empirical performance is, in itself, a significant contribution.\n\nWe hope these clarifications address your concerns. Additionally, we will revise the paper to improve presentation, including defining multi-objective EAs in the introduction, adding intuitive proof explanations, and clarifying that a linear cost constraint refers to a knapsack constraint. \n\nPlease do not hesitate to reach out if you have further questions or suggestions. Thank you very much.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence", "methods_and_evaluation_criteria": "Proposed methods and evaluation criteria make sense for the problem or application at hand.", "theoretical_claims": "No apparent issue found.", "experimental_designs_or_analyses": "Empirical evaluation is conducted on maximum coverage and influence maximization with six datasets. The results are sound.", "relation_to_broader_scientific_literature": "The paper studies a fundamental combinatorial optimization problem: monotone submodular maximization under knapsack constraints. It improves the state-of-the-art approximation ratio achieved by evolutionary algorithms (EAs) from $(1-1/e)/2$ to $0.6174$, marking a significant advancement in the field.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "In this work, the authors re-analyze POMC and demonstrate that it achieves a $1/2$ approximation ratio. By repeatedly running POMC with a 1-guess technique, this approximation ratio is further improved to $0.6174$. However, the technical contribution of the paper appears to be somewhat limited, as the primary advancements rely on modifications and repeated applications of existing methods rather than introducing fundamentally new algorithmic ideas.\n\nMoreover, the algorithm sections consist primarily of lengthy proofs without sufficient discussion of the high-level ideas. This makes it challenging for readers to grasp the intuition behind the proposed methods. The presentation of the paper could be significantly improved by including more intuitive explanations and balancing technical details with conceptual insights.", "other_comments_or_suggestions": "- A linear cost constraint is typically referred to as a knapsack constraint in the literature.\n\n- The paper does not provide a clear definition of what a multi-objective EA is in the introduction or preliminary.\n\n- The core idea behind improving the approximation ratio of POMC should be introduced at a high level at the beginning of Section 3 to provide readers with a clear understanding of the approach before delving into technical details.", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aN16lO7ORU", "reviewer": "Reviewer_JmGW", "summary": "This paper studies the problem of subset selection with a linear cost constraint. The authors first improved the approximation guarantee (from (1-1/e)/2 to 1/2) of an existing evolutionary algorithm, so-called POMC, with the best empirical performance. Then, they proposed a new evolutionary algorithm EPOL with a better approximation guarantee of 0.6174. They also performed experiments on two applications (maximum coverage and influence maximization), showing that EPOL can achieve significantly better performance in most cases.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable suggestions. We sincerely appreciate your feedback, which will help us improve our manuscript. Below are our detailed responses to your queries.\n\n---\n\n> ... more explanations. Why the formulas in cases (1)-(3) satisfy Equation (6) with $i +c(v^*)$?\n\nThank you for your suggestion. We will include a more detailed explanation after analyzing cases (1)–(3) as follows:\n\nBy combining the inequalities derived from cases (1)–(3), we can conclude that the new solution $X' = X \\cup v^*$ satisfies:\n\n$f(X') \\geq \\left(1 - e^{-\\frac{\\min\\\\{i+c(v^*), J\\\\}}{B-c(o_c)}}\\right) \\cdot \\left(f(X^*) - f(o_c)\\right) + \\frac{\\max\\\\{i+c(v^*)-J, 0\\\\}}{B-c(o_c)} \\cdot z(r) \\cdot f(X^*)$. \n\nAdditionally, the cost of solution $X'$ satisfies $c(X') = c(X) + c(v^*) \\leq i + c(v^*)$. Consequently, the solution $X'$ must be included in $P$; otherwise, $X'$ must be dominated by one solution in $P$ (line 6 of Algorithm 1). This  implies that $J_{max}$  has already exceeded $i$, contradicting the assumption that $J_{max} = i$. Hence, after including $X'$, we have $J_{max} \\geq i + c(v^*)$.\n\n---\n\n> ... Did you consider $i+c(v^*)>B-c(o_c)$, which will contradict with $J_{max}\\leq B-c(o_c)$?\n\nYes, we did consider this case. On page 5, second column, starting from line 251, we addressed the situation where the inclusion of the new solution $X'$ causes $J_{max} + c(v^*)$ to exceed $B - c(o_c)$, i.e., $J_{max} \\leq B - c(o_c) < J_{max} + \\delta \\leq J_{max} + c(v^*)$. In this situation, we can deduce that $X'$ is a $(1 - z(r))$-approximation solution. We will further clarify this point in the revised manuscript. Thank you.\n\n---\n\n> “... greedy algorithms that obtain the theoretical optimal approximation of 1 − 1/e” ... Why are these algorithms impractical? \n\n[Sviridenko, 2004] developed a $(1-1/e)$-approximation algorithm by selecting three optimal elements and using a greedy approach, but it has a high time complexity of $O(n^5)$. Later, [Badanidiyuru & Vondrák, 2014] and [Ene & Nguyen, 2019] proposed greedy-based algorithms that achieve a $(1-1/e-\\epsilon)$-approximation. However, their computational costs remain prohibitively high, with time complexities of $O(n^2(\\frac{\\log n}{\\epsilon})^{O(1/\\epsilon^8)})$ and $(1/\\epsilon)^{O(1/\\epsilon^4)}n\\log^2n$, respectively. These complexities render the algorithms impractical for real-world applications. These details will be clarified in the introduction. Thank you.\n\n---\n\n> ...only a subset of residual problems corresponding to the items with large values are enumerated. ... But I still would like to see the performance of the full version of EPOL. Can it bring further improvement?  \n\nIn our experiments, we enumerated a subset of residual problems to balance computational efficiency and performance. We agree that evaluating the full version of EPOL, is both interesting and necessary. Thanks to your suggestion, we conducted additional experiments comparing the original EPOL (as in the manuscript) and the full version (EPOL-full), which enumerates all residual problems. For $q = 5$, the objective values (avg $\\pm$ std) on maximum coverage for three datasets are summarized in the tables. For each budget $B$, the larger value is bolded, and ‘$\\bullet$’ indicates that EPOL-full significantly outperforms EPOL (Wilcoxon signed-rank test, confidence level 0.05). The results highlight EPOL-full’s potential to improve performance by addressing all residual problems, consistently outperforming EPOL with significant advantages in several cases.\n\nWe will revise the manuscript to include these results and discussions. Thank you for your valuable feedback.\n\n| Budget $B$| $300$| $350$  | $400$ |   $450$|$500$  |\n| - | :--: | :--: | :--: | :--: | :--: |\n| **frb-30-15-1:** | \n|EPOL|301.1 $\\pm$ 1.0 $\\bullet$| 329.7 $\\pm$ 0.5 $\\bullet$ |354.4 $\\pm$ 0.9|375.2 $\\pm$ 1.5 $\\bullet$|394.1 $\\pm$ 1.8|\n|EPOL-full|**302.1 $\\pm$ 0.8**|**330.9 $\\pm$ 0.3**|**354.8 $\\pm$ 0.4**|**377.3 $\\pm$ 1.3**|**395.2 $\\pm$ 1.1**|\n| **frb-35-17-1:** | \n|EPOL|319.1 $\\pm$ 0.8|356.6 $\\pm$ 0.9 $\\bullet$|389.8 $\\pm$ 0.6 $\\bullet$|419.0 $\\pm$ 0.6| 445.7 $\\pm$ 0.6 $\\bullet$|\n|EPOL-full|**319.8 $\\pm$ 0.4**|**357.9 $\\pm$ 0.3**|**390.6 $\\pm$ 0.5**|**419.4 $\\pm$ 0.3**|**446.5 $\\pm$ 0.5**|\n| **congress:** |  \n|EPOL|332.8 $\\pm$ 0.4|358.0 $\\pm$ 0.6 $\\bullet$|381.2 $\\pm$ 0.6|399.9 $\\pm$ 0.7|415.5 $\\pm$ 0.5 $\\bullet$|\n|EPOL-full|**333.4 $\\pm$ 0.5**|**359.0 $\\pm$ 0.6**|**381.4 $\\pm$ 0.7**|**400.2 $\\pm$ 1.0**|**416.1 $\\pm$ 0.5**|\n\n---\n\n> Why is the objective evaluation noisy for the application of influence maximization?\n\nThe objective evaluation for influence maximization, i.e., $E[|IC(X)|]$, is noisy because the propagation process is randomized, and we use the average of multiple Monte Carlo simulations to estimate the expectation. Specifically, starting from a solution $X$, we simulate the propagation 500 times and use the average as the estimated objective value.  We will revise to make it clear. Thank you.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence. The improved approximation guarantee of the existing algorithm POMC and the approximation guarantee of the newly proposed algorithm EPOL are proved mathematically and correctly. The best empirical performance of EPOL has been clearly shown by extensive experiments. The authors compared EPOL with a large number of previous methods on the studied subset selection problem.", "methods_and_evaluation_criteria": "The studied problem of subset selection with a linear cost constraint, where the objective function is monotone submodular, has wide applications and has been studied extensively. This work improves the approximation guarantee of a previous algorithm (with the best observed performance in experiments) and proposes a new better algorithm both theoretically and empirically. The theoretical analysis is rigorous, and the experiments use common benchmark data sets and compare all state-of-the-art works.  I think the proposed methods and/or evaluation criteria make sense.", "theoretical_claims": "I have checked all the proofs (including the proof of a lemma in the appendix) carefully. The improved approximation guarantee of POMC mainly lies in a tighter analysis of the objective improvement by adding a single item. The proof is mainly accomplished by iteratively adding proper single items. The approximation bound of EPOL is proved by considering the residual problem corresponding to the item having the largest objective value in the optimal solution, which must be generated by enumerating all residual problems.\n\nI almost did not find any mistakes. The proofs are presented clearly. I have only some minor questions or suggestions.\n\n- page 5, first column, line 248, I suggest using $J \\geq i+c(v^*)$, to be consistent with the presentation in cases (2) and (3).\n- page 5, second column, “This implies that $J_{\\max}$ has already exceeded $i$” I suggest adding more explanations. Why the formulas in cases (1)-(3) satisfy Equation (6) with $i+c(v^*)$?\n\n- page 5, second column, “After including … $J_{\\max} \\geq i+c(v^*)$” Did you consider $i+c(v^*) > B-c(o_c)$, which will contradict with $ J_{\\max} \\leq B-c(o_c)$?", "experimental_designs_or_analyses": "Yes, I checked the experimental parts. The proposed algorithm is compared with a series of existing algorithms for the studied subset selection problem, including greedy and evolutionary algorithms. Two applications of subset selection with various parameter settings are tested. The authors performed a significance test, showing that the proposed EPOL algorithm is significantly better in most cases, and never significantly worse. They also conducted some ablation studies, e.g., comparing with multiple runs of the POMC algorithm on the original problem.", "relation_to_broader_scientific_literature": "The studied problem, subset selection, has wide applications across various areas such as machine learning, data mining, and computer networks. This paper proposes a new evolutionary algorithm with better theoretical guarantees and empirical performance. Another contribution of this work is improving the approximation bound of the existing evolutionary algorithm (which performed the best empirically for the subset selection problem). As far as I can tell, this work will bring some influence to the topic of both subset selection and evolutionary computation.", "essential_references_not_discussed": "The related works are properly cited.", "other_strengths_and_weaknesses": "Overall, this is a solid work with both theoretical analysis and empirical evaluation. It makes a good contribution to solving the significant problem of subset selection.", "other_comments_or_suggestions": "The paper is well written. Some minor issues:\n\n- page 1, second column, line 38-40, “further optimizes this approach” -> “further improves this approach”\n\n- page 2, first column, line 107, “objective” -> “objective evaluation”\n\n- page 4, second column, line 183, “Lemma 3.2” -> “The proof of Lemma 3.2”\n\n- page 4, the function $z$ in Theorem 3.1 is defined in Lemma 3.4 after its first appearance. I suggest giving the definition first.\n\n- page 7, first column, $/N\\delta$ -> $/(N\\delta)$\n\n- page 7, first column, line 374, budget $B$ -> the budget $B$\n\n- page 8, first column, line 417-419, “search” -> “searches” “maintain” -> “maintains”\n\n- page 8, second column, line 400, “, additional” -> “. Additional”\n\n- page 8, second column, line 407, “performs best” -> “performs the best” Please check throughout the paper, e.g., the same issue in page 12.\n\n- page 8, second column, line 413, “, shows” -> “, which shows”\n\n- page 9, first column, line 449, “EA POMC” -> “EA, POMC”\n\n- page 11, line 573, “Combing” -> “Combining”\n\n- page 11, line 587, “,and” -> “, and”\n\n- page 12, “conclude those” ?\n\n- caption of Table 10, “the probability of each 0.05” ?\n\n- page 16, line 831, “the optimal objective value” -> “the best objective value”", "questions_for_authors": "1. In the introduction part, you mentioned “While there are greedy algorithms that obtain the theoretical optimal approximation of 1 − 1/e, they are generally impractical due to high computational costs” I’d like to see more explanations. Why are these algorithms impractical?\n\n2. The proposed EPOL algorithm enumerates all the $n$ residual problems by excluding each single item. But in the experiments, only a subset of residual problems corresponding to the items with large $f$ values are enumerated. The authors did not give any explanation. I can understand this setting is sufficient to show the superiority of the proposed EPOL as the implemented version is weaker. But I still would like to see the performance of the full version of EPOL. Can it bring further improvement?\n\n3. Why is the objective evaluation noisy for the application of influence maximization?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p9dgLJ3kXE", "reviewer": "Reviewer_vZX8", "summary": "This paper contributed to 1) analyzing the existing approach for submodular optimization with a linear inequality constraint, and 2) proposing a novel approach with a better approximation guarantee and better practical performance. This paper first analyzed the existing approach, POMC, an evolutionary algorithm that maintains a population of non-dominated solutions where the constraint is treated as the second objective. The analysis of this paper improves the existing theoretical guarantee by a constant factor (from 0.5(1 - 1/e) to 0.5). The rigorous proof is provided in the main text, followed by a description of the difference in the proof from the proof of the existing result. Then, the authors propose a novel approach, EPOL, which simply repeats running POMC for subproblems that are constructed by removing each element. The theoretical analysis revealed the improved theoretical guarantee (from 0.5 to 0.61...). The empirical study shows that the proposed approach is not only theoretically improved, but also performs better than existing approaches over different test problems.\n\n## update after rebuttal\n\nAll my concerns have been addressed during the rebuttal phase. I keep my initial score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive feedback and encouraging validation of our work's strengths. Please find our detailed responses below.\n\n---\n\n> The discussion about the potential real-world applications would improve the visibility of this paper.\n\nThe discussion about the potential real-world applications would enhance the impact and relevance of this paper. The problem studied in this paper is highly relevant to domains where cost-aware resource allocation and the diminishing returns property of objective functions play a key role. It has applications in diverse areas, e.g., combinatorial optimization, computer networks, data mining, and machine learning. Beyond the maximum coverage and influence maximization examined in this paper, potential applications include sensor placement, balancing information gain with installation costs (Krause et al., 2006); recommendation systems, promoting products within advertising budgets while respecting user preferences (Ashkan et al., 2015); data summarization, maximizing information retention under computational resource constraints (Lin & Bilmes, 2011); active learning, selecting maximally informative data samples under limited annotation budgets (Golovin & Krause, 2011); and human-assisted learning, optimizing machine learning models with limited expert resources (De et al., 2020, 2021). We appreciate your suggestion and will incorporate these discussions into the paper. Thank you very much for your suggestion.\n\nReference: \n\nKrause, A., et al. \"Near-optimal sensor placements: Maximizing information while minimizing communication cost.\" Proc. IPSN, 2006.\n\nAshkan, A., et al. \"Optimal Greedy Diversity for Recommendation.\" Proc. IJCAI, 2015.\n\nLin, H., and Bilmes, J. \"A class of submodular functions for document summarization.\" Proc. ACL, 2011.\n\nGolovin, D., and Krause, A. \"Adaptive submodularity: Theory and applications in active learning and stochastic optimization.\" J. AI Research, 2011.\n\nDe, A., et al. \"Regression under human assistance.\" Proc. AAAI, 2020.\n\nDe, A., et al. \"Classification under human assistance.\" Proc. AAAI, 2021.\n\n---\n\n> Empirical results only show the final performance. It seems that different algorithms spent different iterations /function calls / time. Ideally, to compare the performance, the budget (iterations/f-calls/time, etc.) should be the same for all algorithms. Low performance algorithms with fast convergence may be trivially improved by incorporating a restart mechanism.\n\nThank you for your comment. We fully agree, and actually have tried to make the comparison fair. The algorithms in our study fall into two categories: fixed-time algorithms such as GGA, Greedy$^+$, and 1-guess Greedy$^+$, with runtime complexities of $O(nK_B)$, $O(nK_B)$, and $O(n^2K_B)$, respectively, and anytime algorithms such as POMC, EAMC, FPOMC, and EVO-SMC, whose performance improves with increased runtime. To ensure a fair comparison, we allocated the same number of objective function evaluations ($20nK_B$) to all anytime algorithms. EPOL decomposes the original problem into $K_B$ subproblems and solves them in parallel using POMC, allocating a budget of $20nK_B$ evaluations to each subproblem. Furthermore, we also compared EPOL with a variant of POMC, called P-POMC, as described in Appendix B.4. P-POMC directly runs the original problem on $K_B$ parallel processors, where each processor is also allocated a budget of $20nK_B$ evaluations. Our experimental settings align with prior work in the literature [Bian et al., 2020, Roostapour et al., 2022, Zhu et al., 2024]. It is worth noting that fixed-time algorithms (GGA, Greedy$^+$, and 1-guess Greedy$^+$) cannot benefit from restart mechanisms, as they always return the same solution for a given input. We will revise to make them clear. Thank you very much.\n\n---\n\n> The theoretical guarantee doesn't seem to match the practical performance, hence the improvement in theoretical guarantee does not necessarily imply the improvement in practice, hence its value is a bit questionable.\n\nGood point! Yes, the theoretical guarantee of an algorithm may not match its practical performance. This is because the theoretical guarantee implies the approximation performance in the worst case, which may differ from the tested real-world cases. Thus, it is possible that two algorithms with the same theoretical guarantee may demonstrate different performances in practice. However, a good theoretical guarantee is still important, which guarantees the worst-case performance of an algorithm and can characterize the robustness of the algorithm. Thus, a good algorithm should have both good theoretical guarantee and empirical performance. Our proposed algorithm EPOL has this property, which not only achieves the best-known practical theoretical guarantee, but also demonstrates empirical advantages across different settings. We will revise to add more explanation to make them clear. Thank you very much for your suggestion.", "claims_and_evidence": "Their claims, improving theoretical guarantee of EAs for subset selection problem with a monotone and submodular objective function under a linear cost constraint as well as improving their practical performance, are supported by rigorous theoretical results and thorough experimental results.", "methods_and_evaluation_criteria": "Methodologies and Experimentation looks valid. However, honestly, as I am not familiar with this specific problem class, I am not fully sure about my assessment.", "theoretical_claims": "I did check the proof and didn’t find any flaw.", "experimental_designs_or_analyses": "Empirical results only show the final performance. It seems that different algorithms spent different iterations / function calls / time. Ideally, to compare the performance, the budget (iterations/f-calls/time, etc.) should be the same for all algorithms. Low performance algorithms with fast convergence may be trivially improved by incorporating a restart mechanism.\n\nAs I am not familiar with this topic itself, I am not sure whether the experiments done in this paper meet the standard of the community.", "relation_to_broader_scientific_literature": "The discussion about the potential real-world applications would improve the visibility of this paper.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\n- Improved theoretical results with rigorous and non-trivial proofs\n\n- Strong empirical results showing superior performance of the proposed approach over different baselines on different problems\n\nWeaknesses:\n\n- The theoretical guarantee doesn't seem to match the practical performance, hence the improvement in theoretical guarantee does not necessarily imply the improvement in practice, hence its value is a bit questionable.\n\n- Empirical results only show the final performance. It seems that different algorithms spent different iterations / function calls / time. Ideally, to compare the performance, the budget (iterations/f-calls/time, etc.) should be the same for all algorithms. Low performance algorithms with fast convergence may be trivially improved by incorporating a restart mechanism.", "other_comments_or_suggestions": "The sizes of parentheses could be reconsidered for better presentation.", "questions_for_authors": "Please read the “Other Strengths And Weaknesses” part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YXKd4tq2XB", "reviewer": "Reviewer_sMVc", "summary": "The manuscript presents an advanced study on subset selection problems, which are prevalent in various fields such as machine learning, operations research, and economics. The authors focus on subset selection under a linear cost constraint, a problem characterized by its NP-hardness and practical importance. The paper introduces an improved theoretically-grounded evolutionary algorithm (EA), enhancing the performance of the Pareto Optimized Multi-Criteria (POMC) algorithm and proposing a novel multi-objective EA, named EPOL.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and for recognizing the strengths of our work. We appreciate your kind words regarding our contributions and writing. Please find our detailed responses below.\n\n---\n\n> I understand that this work is mainly a theoretical contribution, but if we can compare more SOTA algorithms, we can further demonstrate the superiority of the algorithms.\n\nThank you for your valuable suggestion. To the best of our knowledge, we have already included all state-of-the-art algorithms relevant to our problem setting in our comparisons. Nonetheless, we appreciate your perspective and will explore further comparisons in future work as more methods become available. Thank you.\n\n---\n\n> How does the proposed EPOL algorithm scale with the size of the problem (e.g., larger ground sets or higher-dimensional feature spaces)? Could the authors provide some insights or preliminary results on scalability?\n\nThank you for your insightful comment. The proposed algorithm is designed to be highly parallelizable, which makes it well-suited for larger-scale problems. Thanks to your suggestion, we compare EPOL against three comparison algorithms—namely, the baseline GGA, the high-performance greedy algorithm 1-guess-Greedy$^+$, and POMC—using a larger network dataset email-Eu-core (1005 vertices, 25,571 edges) on the maximum coverage problem with $q = 5$. For each budget $B$, we calculated the objective values (average $\\pm$ std) and highlighted the best performance in bold. Additionally, a ‘$\\bullet$’ indicates that EPOL significantly outperforms the corresponding algorithm, as confirmed by a Wilcoxon signed-rank test (confidence level 0.05). Consistent with the results reported in the paper, EPOL significantly outperforms other algorithms. Thank you again for your valuable feedback.\n\n|     Budget $B$     |           $300$           |           $350$           |\n| :----------------: | :-----------------------: | :-----------------------: |\n|        GGA         |       525 $\\bullet$       |       575 $\\bullet$       |\n| 1-guess-Greedy$^+$ |       528 $\\bullet$       |       578 $\\bullet$       |\n|        POMC        | 531.3 $\\pm$ 1.3 $\\bullet$ | 581.3 $\\pm$ 0.9 $\\bullet$ |\n|        EPOL        |    **532.8 $\\pm$ 0.4**    |    **582.5 $\\pm$ 0.5**    |\n\n---\n\n> Are there any parameters in the EPOL algorithm that require fine-tuning? If so, how sensitive are the results to these parameters?\n\nWe would like to clarify that the design of the EPOL algorithm inherently avoids the need for fine-tuning of parameters. This feature contributes to its robust and consistent performance across various settings. Thank you.\n\n---\n\n> The empirical study focuses on maximum coverage and influence maximization. Would the authors consider extending the study to other relevant problems such as budgeted submodular optimization?\n\nThank you for your insightful comment. While our empirical study has primarily focused on maximum coverage and influence maximization, our methodology is inherently adaptable to budgeted submodular optimization problems in scenarios where cost-aware resource allocation and the diminishing returns property of objective functions are central concerns. For instance: sensor placement, which balances information gain with installation costs (Krause et al., 2006); recommendation systems, which promote products within advertising budgets and respect user preferences (Ashkan et al., 2015); data summarization, which maximizes information retention under computational resource constraints (Lin & Bilmes, 2011); active learning, which selects maximally informative data samples under limited annotation budgets (Golovin & Krause, 2011); and human-assisted learning, which optimizes machine learning models with limited expert resources (De et al., 2020, 2021). As suggested by Reviewer vZX8, we will revise the paper to include more discussions on the applications of the studied problem, thereby improving its visibility. Thank you very much.\n\nReference: \n\nKrause, A., et al. \"Near-optimal sensor placements: Maximizing information while minimizing communication cost.\" Proc. IPSN, 2006.\n\nAshkan, A., et al. \"Optimal Greedy Diversity for Recommendation.\" Proc. IJCAI, 2015.\n\nLin, H., and Bilmes, J. \"A class of submodular functions for document summarization.\" Proc. ACL, 2011.\n\nGolovin, D., and Krause, A. \"Adaptive submodularity: Theory and applications in active learning and stochastic optimization.\" J. AI Research, 2011.\n\nDe, A., et al. \"Regression under human assistance.\" Proc. AAAI, 2020.\n\nDe, A., et al. \"Classification under human assistance.\" Proc. AAAI, 2021.", "claims_and_evidence": "yes, this paper has made complete proofs for all Lemmas.", "methods_and_evaluation_criteria": "yes, this work  deepens the theoretical understanding of EAs.", "theoretical_claims": "yes, i have checked the proofs of Lemma 3.2 and 3.3", "experimental_designs_or_analyses": "yes, the experimental designs and analyses are abundant.", "relation_to_broader_scientific_literature": "yes, there remains a gap in the approximation bounds of EAs compared to greedy algorithms, and their full theoretical potential is yet to be realized.", "essential_references_not_discussed": "this paper provides a theoretical understanding of EAs, which has not been discussed in previous literatures.", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper makes a significant theoretical contribution by improving the approximation guarantee of the POMC algorithm to 1/2, which is a substantial advancement in the field.\n\nThe proposed EPOL algorithm is innovative and achieves the best-known practical approximation guarantee of 0.6174, which is a notable empirical performance.\n\nThis work not only advances the subset selection problem but also deepens the theoretical understanding of EAs.\n\nThe writing is clear and the mathematical formulation is precise, making the paper accessible to readers familiar with evolutionary algorithms and optimization.\n\nWeaknesses:\n\nThe manuscript would benefit from a more detailed comparison with other state-of-the-art algorithms in the literature, especially in terms of computational complexity and scalability.\n\nThe discussion on the limitations of the proposed methods is somewhat brief. A more in-depth analysis could provide insights into potential improvements or alternative applications.\n\nI understand that this work is mainly a theoretical contribution, but if we can compare more SOTA algorithms, we can further demonstrate the superiority of the algorithms.", "other_comments_or_suggestions": "None", "questions_for_authors": "How does the proposed EPOL algorithm scale with the size of the problem (e.g., larger ground sets or higher-dimensional feature spaces)? Could the authors provide some insights or preliminary results on scalability?\n\n\nAre there any parameters in the EPOL algorithm that require fine-tuning? If so, how sensitive are the results to these parameters?\n\nThe empirical study focuses on maximum coverage and influence maximization. Would the authors consider extending the study to other relevant problems such as budgeted submodular optimization?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work studies evolutionary algorithms (EAs) for monotone submodular maximization subject to a linear cost constraint. In particular, it:
- improves the analysis of the approximation ratio for the POMC EA [Qian et al., IJCAI 2017] from $1/2 \cdot (1 - 1/e)$ to $0.5$,
- proposes a new multi-objective EA called EPOL, which achieves an approximation ratio of $0.6174$, matching that of the best-known (combinatorial) greedy algorithm.
The paper is well written, gives clean proofs for all results, and presents a compelling set of experiments.

The majority of reviewers are in favor of "accept" (scores: [2, 4, 4, 4]). The reviewer who recommended "weak reject" did not respond to the authors' rebuttal, so our final recommendation for this paper is acceptance.
Decision: Accept (poster)