Robust Subset Selection by Greedy and Evolutionary Pareto Optimization

1 Introduction

The subset selection problem is to select a subset of size at most k from a total set of n items for optimizing some objective function f , which arises in many applications, such as influence maximization [Kempe et al., 2003], sensor placement [Krause et al., 2008b], document summarization [Lin and Bilmes, 2011], and unsupervised feature selection [Feng et al., 2019], etc. This problem is NP-hard in general, and much effort has been devoted to the design of polynomialtime approximation algorithms.

The greedy algorithm, which iteratively selects one item with the largest marginal gain on f, is a very popular algorithm for solving the subset selection problem. For a monotone submodular objective function f, it can achieve the optimal polynomial-time approximation guarantee of 1 - 1/e [Nemhauser and Wolsey, 1978]. Due to its highefficiency and theoretically-grounded performance, it is most favored and has been studied extensively [Minoux, 1978; Mirzasoleiman et al., 2015; Hassidim and Singer, 2017; Qian et al., 2018; Friedrich et al., 2019].

∗This work was supported by the NSFC (62022039) and the CAAI-Huawei MindSpore Open Fund. Chao Qian is the corresponding author. The supplementary material is available at https://arxiv.org/abs/2205.01415.

In real-world applications of subset selection, however, we may want to find a subset which is robust against a number of possible objective functions, i.e., the subset is good on the worst of these objective functions. For example, in influence maximization, the influence of a set of social network users has significant uncertainty due to different models and parameters, and the goal is to optimize a set of influence functions simultaneously, in which one function is assured to describe the influence process exactly (but which one is not told) [He and Kempe, 2016]. In sensor placement, sensors are often used to monitor various phenomena such as temperature and humidity at the same time, whose observations are modeled by different functions, and the goal is to find a subset of candidate locations to place sensors such that the sensors can performwell on all the objective functions [Anari et al., 2019].

To address the above more complicated real-world scenario of subset selection, Krause et al. [2008a] considered the robust subset selection problem

argmaxX⊆V min1≤i≤m fi(X) s.t. |X| ≤ k, (1) where f1, f2, . . . , fm are monotone submodular objective functions and | · | denotes the size of a set. They proved that there cannot exist any polynomial time approximation algorithm unless P=NP, and proposed an algorithm SATURATE, which can find a subset matching the optimal worst-case objective value but with size larger than k. Anari et al. [2019] extended the cardinality constraint |X| ≤ k in Eq. (1) to a matroid constraint, and provided a bi-criteria algorithm which can find O(log(m/ϵ)) feasible subsets whose union achieves an approximation ratio of 1 - ϵ, where ϵ ∈ (0, 1). Udwani [2018] designed a fast and practical algorithm for the case of m = o(k). He and Kempe [2016] modified SATURATE for the application of robust influence maximization, and showed that a (1 - 1/e)-approximation ratio can be achieved when enough extra seed users may be selected. Iyer [2019] considered both robust submodular minimization and maximization problems, and proposed a general framework to transform the algorithm for one problem to the other.

Recently, Hou and Clark [2021] introduced the notion of correlation ratio and proposed a modified greedy algorithm which can achieve an approximation guarantee with respect to the correlation ratio.

Note that all the above-mentioned previous studies considered monotone submodular objective functions. However, the objective functions of some applications such as influence maximization under general cascade model [Kempe et al., 2003] and sparse regression [Das and Kempe, 2011] can be non-submodular. This paper thus considers the problem of robust subset selection with monotone objective functions, that is, f1, f2, . . . , fm are monotone but not necessarily submodular. First, we show that the classic greedy algorithm which iteratively adds one item maximizing the gain on the worstcase objective function can achieve an approximation ratio of 1-e-β γ , where β and γ are the correlation ratio (slightly different from that proposed in [Hou and Clark, 2021]) and the submodularity ratio of the objective functions, respectively.

Though the greedy algorithm is efficient and theoretically grounded, its performance may be limited in practice due to the greedy nature. Next, we propose an evolutionary Pareto optimization algorithm, EPORSS, which is an anytime algorithm that can use more time to find better subsets. EPORSS first reformulates the original robust subset selection problem as a bi-objective optimization problem that maximizes min1≤i≤m fi and minimizes the subset size simultaneously, then employs a multi-objective evolutionary algorithm to solve it, and finally selects the best feasible solution (i.e., subset) from the generated population. We prove that EPORSS can achieve an approximation ratio similar to that of the greedy algorithm.

The submodularity ratio γ has been analyzed before (e.g., [Bian et al., 2017; Elenberg et al., 2018; Qian et al., 2019]), and here we prove a lower bound of the correlation ratio β for the application of robust influence maximization, to show the applicability of the derived approximation guarantees of the greedy algorithm and EPORSS. Experimental results on robust influence maximization show that the greedy algorithm can achieve competitive performance to the well-known algorithm SATURATE, but requires less time; EPORSS using more time can achieve superior performance over the greedy algorithm and SATURATE. Therefore, these two algorithms can be used under the limited and abundant computation budgets, respectively, helping solve diverse practical problems of robust subset selection better.

2 Preliminaries

Given a finite nonempty set V = {v1, v2, . . . , vn}, we study the functions f : 2V → R defined on subsets of V . A set function f is monotone if for any X ⊆ Y , f(X) ≤ f(Y ). In this paper, we consider monotone functions and assume that they are normalized, i.e., f(∅) = 0. A set function f is submodular [Nemhauser et al., 1978] if for any X ⊆ Y ⊆ V ,

The submodularity ratio in Definition 1 characterizes how close a set function f is to submodularity. For a monotone function f, it holds that 0 ≤ γX,b(f) ≤ 1, and f is submodular iff γX,b(f) = 1 for any X and b. For some concrete non-submodular applications, lower bounds on γX,b(f) have been derived [Bian et al., 2017; Elenberg et al., 2018; Qian et al., 2019]. When f is clear, we will omit f and use γX,b for short.

Definition 1 (Submodularity Ratio [Das and Kempe, 2011]). Let f be a non-negative set function. The submodularity ratio of f with respect to a set X and a parameter b ≥ 1 is

The subset selection problem as presented in Definition 2 is to select a subset X of V such that a given monotone objective function f is maximized with the constraint |X| ≤ k, where | · | denotes the size of a set.

Definition 2 (Subset Selection). Given a set of items V = {v1, v2, . . . , vn}, a monotone objective function f , and a budget k, to findargmaxX⊆V f(X) s.t. |X| ≤ k.

It has many applications such as influence maximization [Kempe et al., 2003] and sensor placement [Krause et al., 2008b]. Influence maximization is to select a subset of users from a social network to maximize its influence spread, which often appears in viral marketing. Sensor placement is to select a few places to install sensors such that the uncertainty is mostly reduced, which often appears in spatial monitoring of certain phenomena.

The original subset selection problem in Definition 2 considers optimizing only one objective function. However, in real-world scenarios, one may need to find a subset which performs well on a number of possible objective functions. For example, in viral marketing, the company may want to identify a set of users to promote several products (e.g., shirts and sweaters) simultaneously, while the influences of users on different products can be different [Kalimeris et al., 2019]; even for one product, perturbations or uncertainty regarding the parameters of diffusion models will result in different objective functions. In spatial monitoring of certain phenomena, sensors are often used to measure various parameters such as temperature and humidity at the same time, giving rise to different objective functions [Anari et al., 2019]; besides, the data obtained in real world is often noisy, which will lead to perturbations on the objective functions. In both above-mentioned applications, we need to find a subset that is robust against all the possible objective functions, i.e., optimize the worst of these objective functions. More evidences can be seen on the applications of robust column subset selection [Zhu et al., 2015] and robust sparse regression [Thompson, 2022]. In this paper, we focus on the general robust subset selection problem, presented as follows.

Definition 3 (Robust Subset Selection). Given a set of items V = {v1, v2, . . . , vn}, m monotone objective functions f1, f2, . . . , fm, and a budget k, to find

where F (X) = min1≤i≤m fi(X) denotes the worst-case objective value of X.

This problem is very hard even when the objective functions f1, f2, . . . , fm satisfy the submodular property, because it has been proved that polynomial-time algorithms cannot achieve any constant approximation ratio. By introducing a quantity β∗ , which reflects the correlation of the objective functions, Hou and Clark [2021] proposed the modified greedy algorithm with an approximation ratio of 1 - e-β∗ . If allowing the subset size larger than k, Krause et al. [2008a] showed that the SATURATE algorithm can achieve the optimal F value.

Note that the correlation of the objective functions relies on the behavior of the modified greedy algorithm [Hou and Clark, 2021]. Here we generalize this notion in Definition 4, which will be used in our theoretical analysis. Intuitively, the correlation ratio reflects the similarity of the objective functions to be optimized. A large correlation ratio implies that all the objective functions can be improved substantially by adding a common item into the subset X. For monotone objective functions, 0 ≤ βX ≤ 1, and βX = 1 means that there exists one common item, adding which makes all the functions achieve the largest improvement.

Definition 4 (Correlation Ratio). The correlation ratio of functions f1, f2, . . . , fm with respect to a set X is

where vi ∈ arg maxv∈V \X fi(X ∪ {v}).

3 The Greedy Algorithm

To solve the robust subset selection problem, a nature way is to apply the greedy process. As shown in Algorithm 1, the greedy algorithm iteratively adds one item with the largest improvement on F until k items are selected. Let OPT = maxX⊆V,|X|≤k F(X) denote the optimal function value of the problem in Definition 3, and Xj (0 ≤ j ≤ k) denote the subset generated in the j-th iteration (note that X0 = ∅) of Algorithm 1. We prove in Theorem 1 that the greedy algorithm can achieve an approximation ratio of 1 - e-β γ , where β = min0≤j≤k-1 βXj denotes the minimum correlation ratio with respect to the first k subsets generated by the greedy algorithm, and γ = min1≤i≤m γXk-1,k(fi) denotes the minimum submodularity ratio of all the objective functions with respect to Xk-1 and k.

Theorem 1. For robust subset selection in Definition 3, the greedy algorithm finds a subset X ⊆ V with |X| = k and

When the number m of functions is 1, i.e., the robust subset selection problem in Definition 3 degrades to the original subset selection problem in Definition 2, we have β = 1, and the approximation ratio becomes 1 - e-γ , which is the optimal polynomial-time approximation guarantee [Harshaw et al., 2019]. When f1, f2, . . . , fm are submodular, we have γ = 1, and the approximation ratio becomes 1 - e-β , which is similar to that achieved by the modified greedy algorithm [Hou and Clark, 2021]. Though the two approximation guarantees cannot be compared exactly due to the slightly

Algorithm 1 Greedy Algorithm

Input: all items V = {v1, v2, . . . , vn}, the objective function F = min1≤i≤m fi, and a budget k

Output: a subset of V with k items

Process:

• 1: Let j = 0 and Xj = ∅;
• 2: while j < k do
• 3: Let v∗ = argmaxv∈V \Xj F(Xj ∪ {v});
• 4: Let Xj+1 =Xj ∪ {v∗ }, and j = j +1
• 5: end while
• 6: return Xk

different definitions of the correlation ratio, our greedy algorithm is faster than the modified greedy algorithm [Hou and Clark, 2021]. The greedy algorithm in Algorithm 1 performs (n - k/2 + 1/2)k number of worst-case objective function evaluations in total, while the modified greedy algorithm needs to first compute the largest improvement on each objective function in each iteration, thus requires extra (n-k/2 + 1/2)k number of worst-case objective function evaluations in total. The detailed procedure of the modified greedy algorithm is provided in the supplementary material due to space limitation.

The proof of Theorem 1 relies on Lemma 2, which intuitively means that for any subset, the inclusion of one specific item can improve F by at least a quantity proportional to the current distance to the optimum. Lemma 1 shows a similar result with respect to a single objective function fi, which will be used in the proof of Lemma 2. The detailed proof of Lemma 2 is provided in the supplementary material due to space limitation.

Lemma 1. [Qian et al., 2016] For any 1 ≤ i ≤ m and X ⊆ V , there exists one item v ∈ V \ X such that

where OPTi = maxX⊆V,|X|≤k fi(X) denotes the optimal function value of the problem in Definition 2 with respect to the objective function fi.

Lemma 2. For any X ⊆ V , there exists one item v ∈ V \ X such that

where γmin X,k = min1≤i≤m γX,k(fi) denotes the minimum submodularity ratio of all the objective functions with respect to X and k.

Proof of Theorem 1. We will show that for any 0 ≤ j ≤ k,

For j = 0, Eq. (2) holds because X0 = ∅ and ∀i : fi(∅) = 0. Suppose that Eq. (2) holds for some j (where 0 ≤ j ≤ k - 1), we will prove that it also holds for j + 1. Let v∗ ∈ argmaxv∈V \Xj F(Xj ∪ {v}). By Lemma 2, we have

where the second inequality is by β = min0≤j≤k-1 βXj ≤ βXj , and γ =min1≤i≤m γXk-1,k(fi) ≤ min1≤i≤m γXj ,k(fi) = γmin Xj,k k due to the fact that γX,b(f) ≤ γY,b(f) for any Y ⊆ X. According to lines 3-4 in Algorithm 1, Xj+1 is generated by combining Xj with v∗ . Thus, we have

where the last inequality holds by the induction hypothesis. Thus, we have shown that Eq. (2) holds for any 0 ≤ j ≤ k. By setting j = k and applying 1 + x ≤ ex for any x ∈ R, the theorem holds.

4 The EPORSS Algorithm

Though the greedy algorithm is efficient and its approximation performance can be theoretically bounded, its performance may be limited in practice due to the greedy nature. Thus, we further propose an Evolutionary Pareto Optimization [Friedrich and Neumann, 2015; Qian et al., 2015] algorithm for Robust Subset Selection, called EPORSS, which can use more time to find better solutions.

Let a Boolean vector x ∈ {0, 1}n represent a subset X of V , where the i-th bit xi = 1 if vi ∈ X and xi = 0 otherwise. For convenience, we will not distinguish x and its corresponding subset. EPORSS reformulates the original problem in Definition 3 as a bi-objective maximization problem:

That is, EPORSS maximizes the original objective F and minimizes the subset size |x| simultaneously. Note that infeasible solutions can cause "shortcuts" and be useful in the evolutionary search, thus g1 only punishes the solutions with size at least 2k so that the infeasible solutions with size belonging to {k+1, . . . , 2k-1} can participate in the optimization process. Meanwhile, too many infeasible solutions may lead to longer runtime, thus the setting of the threshold 2k is to make a tradeoff between performance and runtime.

In the bi-objective setting, the domination relationship in Definition 5 is used to compare two solutions. Note that x and y are incomparable if neither x ⪰ y nor y ⪰ x.

Definition 5 (Domination). For two solutions x and y,

• x weakly dominates y (denoted as x ⪰ y) if g1(x) ≥ g1(y) ∧ g2(x) ≥ g2(y);
• x dominates y (denoted as x ≻ y) if x ⪰ y and g1(x) > g1(y) ∨ g2(x) > g2(y).

EPORSS as described in Algorithm 2 employs a simple multi-objective evolutionary algorithm [Friedrich and Neumann, 2015; Qian et al., 2019] to optimize the bi-objective problem. It starts from the empty set {0}n (line 1). In each iteration, a new solution x′ is generated by applying the bitwise mutation operator to an archived solution x randomly selected from the current population P (lines 3-4); if x′ is not dominated by any previously archived solution (line 5), it will be added into P, and meanwhile those solutions weakly

Algorithm 2 EPORSS Algorithm

Input: all items V = {v1, . . . , vn}, the objective function

F = min1≤i≤m fi, and a budget k

• Parameter: the number T of iterations Output: a subset of V with at most k items Process: 1: Let x = {0}n , P = {x}, and let t = 0; 2: while t < T do 3: Select x from P uniformly at random; 4: Generate x′ by flipping each bit of x with prob. 1/n; 5: if ∄z ∈ P such that z ≻ x′ then 6: P = (P \ {z ∈ P | x′ ⪰ z}) ∪ {x′ } 7: end if 8: t = t +1 9: end while 10: return argmaxx∈P,|x|≤k F(x)

dominated by x′ will be removed (line 6). After running T iterations, the solution with the largest F value satisfying the size constraint in P is selected (line 10).

We can see from the algorithm procedure that EPORSS naturally maintains a population of non-dominated solutions due to the bi-objective transformation. Meanwhile, the bitwise mutation operator for reproduction is a global search operator, which flips each bit of a solution independently with probability 1/n. These characteristics may make EPORSS have a better ability of escaping from local optima than the greedy algorithm. Our experiments will show that EPORSS can find better solutions by using more time. Here, we first show that though using an evolutionary process for optimization, EPORSS can also be theoretically grounded. Particularly, Theorem 2 shows that EPORSS can achieve a similar approximation guarantee as the greedy algorithm. Note that E[T] denotes the expected number T of iterations, γ′ = min1≤i≤mminX:|X|=k-1 γX,k(fi), and β′ = minX:|X|≤k-1 βX .

Theorem 2. For robust subset selection in Definition 3, EPORSS with E[T] ≤ 2ek2n finds a subset X ⊆ V with |X| ≤ k and F (X) ≥ (1 - e-β′ γ ′ ) · OPT.

The proof can be accomplished by following the proof of Theorem 2 in [Qian et al., 2019] and using Lemma 2. The main idea is analyzing the increase of a quantity Jmax, which is defined as the largest number j ∈ {0, 1, . . . , k} such that in the population P, ∃x with |x| ≤ j and F(x) ≥ (1 - (1-β′ γ′ /k)j ) ·OPT. For the sake of completeness, we still provide the full proof in the supplementary material.

5 Analysis of the Correlation Ratio

In the above two sections, we have shown that the approximation performance of the greedy algorithm and EPORSS can be theoretically bounded. However, the approximation guarantees depend on the submodularity ratio γX,b in Definition 1 and the correlation ratio βX in Definition 4. Previous studies have shown that the lower bound on γX,b can be derived for several non-submodular objective functions [Bian et al., 2017; Elenberg et al., 2018]. In this section, we further derive a lower bound on βX for the application of robust influence maximization, showing the applicability of the derived approximation guarantees.

Influence maximization is to identify a set of influential users in social networks. Let a directed graph G(V,E) represent a social network, where each node represents a user and each edge (u, v) has a probability pu,v representing the strength of influence from user u to user v. As presented in Definition 6, the goal is to find a subset X with size at most k such that the expected number (denoted as σ(X)) of nodes activated by propagating from X is maximized.

Definition 6 (Influence Maximization). Given a directed graph G(V,E), edge probabilities pu,v where (u, v) ∈ E is an edge, and a budget k, to find

Independence Cascade (IC) is a fundamental propagation model [Kempe et al., 2003] to estimate the influence function σ, and will also be used in our analysis. Starting from a seed set X, it uses a set At to record the nodes activated at time t, and at time t + 1, each inactive neighbour v of u ∈ At becomes active with probability pu,v. This process is repeated until no nodes get activated at some time. Under the IC model, the objective function σ is monotone submodular [Kempe et al., 2003].

For robust influence maximization, we are given several probability vectors θ1 , θ2 , . . . , θm, where each θ corresponds to a set of edge probabilities, and thus determines a specific influence function, denoted as σθ. The goal is to maximize the worst of the m influence functions σθ1 , σθ2 , . . . , σθm, as shown in the following definition.

Definition 7 (Robust Influence Maximization [He and Kempe, 2016; Kalimeris et al., 2019]). Given a directed graph G(V,E), m probability vectors θ1 , θ2 , . . . , θm, and a budget k, to find

Theorem 3 gives a lower bound on βX for this application. The proof relies on Lemma 3, which intuitively means that when two probability vectors are close, the difference of the influence spread determined by these two vectors can also be small. Lemma 3 is inspired from [Chen et al., 2016], but slightly refined. The detailed proof is provided in the supplementary material due to space limitation, and we introduce the main proof idea here. Under the IC model, the influence spread σθ(X) can be calculated as ∑S⊆G πθ(S) · σS(X) [Kempe et al., 2003], where πθ(S) denotes the probability of sampling a subgraph S from G according to the edge probability vector θ, that is, each edge (u, v) ∈ E appears in S with probability pu,v; and σS(X) denotes the number of nodes that can be reachable fromX on the given subgraph S, which is deterministic when S is given. When two probability vectors only have little difference, the probabilities of sampling a specific subgraph are also slightly different, leading to the similar influence spread.

Lemma 3. For any two probability vectors θ and θ′ , let δ(θ, θ′ ) = ∑i |θi - θ′i | denote the difference between the two vectors, where θi and θ′i denote the i-th element of θ and

θ′ , respectively, and | · | denotes the absolute value of a real number. Then, for any X ⊆ V , we have |σθ(X)-σθ′ (X)| ≤ n · δ(θ, θ′ ), where n denotes the size of V .

Theorem 3 shows that βX can be lower bounded by 1 - 2en·δmax. This is intuitive, because δmax measures the difference among the probability vectors, and thus the corresponding objective functions, while βX characterizes the similarity among the objective functions. Thus, a smaller δmax will lead to a larger lower bound on βX. The proof is accomplished by analyzing the ratio of marginal gains on σθi by respectively adding v1 and vi to X, where v1 and vi are the items whose inclusion in X can make σθ1 and σθi achieve the largest improvement, respectively. The detailed proof is provided in the supplementary material due to space limitation.

Theorem 3. For robust influence maximization in Definition 7, let δmax = max1≤i,j≤m,i̸=j δ(θi , θj ) denote the maximum difference among the m probability vectors. Then, for any X ∈ {X0, X1, . . . , Xk-1}, we have βX ≥ 1-2en·δmax, where Xj (0 ≤ j ≤ k - 1) denotes the subset generated in the j-th iteration (note that X0 = ∅) of Algorithm 1.

6 Experiments

In this section, we empirically compare the performance of the greedy algorithm, EPORSS and two previous algorithms, modified greedy [Hou and Clark, 2021] and SATURATE [Krause et al., 2008a], on the application of robust influence maximization. As suggested in [Krause et al., 2008a], we set the parameter α of SATURATE to 1 such that the output subset will not violate the cardinality constraint. The number of iterations of EPORSS is set to ⌊2ek2n⌋ as suggested by Theorem 2. As EPORSS is randomized, we repeat its run for 10 times independently, and report the average results and standard deviation.

The experiments are performed on two real-world data sets, ego-Facebook and as-733, downloaded from https:// snap.stanford.edu/data/index.html. The ego-Facebook data set contains one network which consists of friend links from Facebook, and we use the perturbation interval method [He and Kempe, 2016] to sample multiple networks with different edge probabilities (which give rise to different objective functions). That is, we first estimate the propagation probability of one edge from node u to v by pu,v = weight(u,v) indegree(v) , as widely used in [Chen et al., 2009; Goyal et al., 2011]; and then sample from the interval [0.9 · pu,v, 1.1 · pu,v] multiple times to obtain different probabilities. For estimating the influence spread, we use the IC model as presented in Section 5, which results in monotone submodular objective functions.

The as-733 data set contains 733 communication networks spanning an interval of 785 days, where the nodes and edges may be added or deleted over time. Thus, the two data sets reflect different causes for uncertainty: the edge probabilities are subject to perturbations, and the influence functions are learned from the networks with different structures. We use the general IC model [Kempe et al., 2003] to estimate the influence spread on as-733. For the general IC model, the probability of activating v by u is pv(u, S) instead of pu,v, where S is the set of neighbours that have already tried (and

(b) as-733

Figure 1: Robust influence maximization on ego-Facebook and as733. The objective F: the worst-case influence spread (the larger, the better). The left subfigure: objective F vs. budget k; the right subfigure: objective F vs. #objectives m.

failed) to activate v. Specifically, for each network in as-733, we set the probability pv(u, S) to min{0.1 + 0.05 · |S|, 1}, i.e., the probability of activating v is 0.1 for the first try, and then the probability increases by 0.05 once a try fails. Note that under the general IC model, the objective functions are generally non-submodular.

For both data sets, we examine the performance of the compared algorithms when the budget k changes from 5 to 10 (where the number m of objective functions is fixed to 3), and also consider the scenario where the number m of objective functions changes from 2 to 6 (where the budget k is fixed to 5). Note that we sample the most active 200 nodes from these two data sets for examination, as in [He and Kempe, 2016]. To estimate the influence spread σ(X) of a subset X of nodes, we simulate the diffusion process 100 times independently and use the average as an estimation. As the objective evaluation is noisy, we also repeat the running of the three deterministic algorithms (i.e., the greedy algorithm, the modified greedy algorithm and SATURATE) 10 times independently and report the average results. We can observe from Figure 1 that the three deterministic algorithms achieve the similar performance, while EPORSS is much better.

Running time comparison. The greedy algorithm in algorithm 1 needs to perform (n-j +1) number of worst-case objective function evaluations in the j-th iteration. Thus, the total running time, i.e., the number of worst-case objective function evaluations, is ∑kj=1 (n-j+1) = (n-k/2+1/2)k. The modified greedy algorithm starts from an empty set, and iteratively adds one item v into the current subset X, such that all the objective functions can be improved as much as possible. However, for each of the m objective functions, the improvement is measured by the ratio of the marginal gain achieved by adding v and the largest possible marginal gain, which needs to be computed in the first place and thus requires extra (n - j + 1) number of objective function evaluations in the j-th iteration. The process terminates after k items are selected. Thus, the total running time is ∑kj=1 2(n - j + 1) = (2n - k + 1)k, i.e., double that of the greedy algorithm. Though the extra objective function evaluations can be avoided by storing the marginal gain achieved by adding each item, extra storage cost is required. SATURATE employs a binary search framework, and each shrink over the search interval needs to perform a greedy subroutine, implying that the running time of SATURATE is substantially larger than that of the greedy algorithm. Thus, the greedy algorithm can achieve competitive performance to the modified greedy algorithm and SATURATE using less time.

EPORSS can achieve the best performance using more time, i.e., 2ek2n iterations. However, 2ek2n is only a theoretical upper bound, which may be too pessimistic in practice. By selecting the three deterministic algorithms (i.e., the greedy algorithm, the modified greedy algorithm and SATURATE) as the baselines, we plot the curve of the objective F over the running time of EPORSS on the two data sets, as shown in Figure 2. The x-axis is in kn, the running time order of the greedy algorithm. It can be observed that EPORSS takes only about 0.9kn and 0.6kn iterations to achieve the best performance on the two data sets, respectively, implying that EPORSS can be more efficient in practice.

7 Conclusion

In this paper, we study the robust subset selection problem with monotone objective functions, and give two algorithms, i.e., the greedy algorithm and the evolutionary Pareto optimization algorithm EPORSS, with bounded approximation guarantees. The experimental results on the application of robust influence maximization show that the greedy algorithm can achieve competitive performance to the previous algorithms, but is more efficient; while EPORSS can achieve better performance by using more time. Thus, these two algorithms can help solve various real-world robust subset selection problems better. Note that we have considered the worstcase running time complexity of EPORSS in theoretical analysis, and the empirical results show that EPORSS can be efficient in practice. Thus, it would be interesting to analyze the average-case running time complexity, which may reflect the practical performance of EPORSS more accurately.