Fast Pareto Optimization for Subset Selection with Dynamic Cost Constraints

1 Introduction

In this paper, we consider the subset selection problem with general cost constraints, i.e.,

where both the objective function f : 2V → R and the cost function c : 2V → R are monotone, but not necessarily submodular. This problem is NP-hard in general, and has various applications, such as influence maximization [Kempe et al., 2003], sensor placement [Krause et al., 2008], document summarization [Lin and Bilmes, 2011] and unsupervised feature selection [Feng et al., 2019], just to name a few.

A well-known special case of this problem is subset selection with cardinality constraints, that is, c(X) = |X|. Das and Kempe [2018] proved that the simple greedy algorithm, which iteratively selects one item from V with the largest marginal gain on f, can achieve the optimal polynomialtime approximation guarantee of (1 - e-γf ) [Harshaw et al., 2019], where γf measures how close f is to submodularity.

∗This work was supported by the National Key Research and Development Program of China (2020AAA0107200), the Fundamental Research Funds for the Central Universities (0221-14380009), the NSFC (62022039, 61876077) and the Australian Research Council (DP160102401). Chao Qian is the corresponding author.

For the general problem Eq. (1), the simple greedy algorithm fails to obtain a bounded approximation ratio [Khuller et al., 1999], while the generalized greedy algorithm can achieve the best known approximation ratio of (αf/2)(1 - e-αf ) [Zhang and Vorobeychik, 2016; Qian et al., 2017], where αf , different from γf , is another notion for measuring the closeness of f to submodularity. Unlike the simple greedy algorithm, the generalized greedy algorithm iteratively selects one item with the largest ratio of the marginal gain on f and c.

As the greedy behavior may limit the performance, Qian et al. [2017] proposed an anytime algorithm POMC by employing a multi-objective evolutionary algorithm (EA) to maximize the objective f and minimize the cost c simultaneously. POMC can find better solutions using more running time in practice. Though it can also achieve the (αf/2)(1 - e-αf )- approximation ratio theoretically, the running time is not polynomially bounded. Thus, Bian et al. [2020] proposed another anytime algorithm EAMC by employing a singleobjective EA to maximize the surrogate objective f (X)/(1e-αfc(X)/B ). EAMC achieves empirical performance competitive with POMC, but can guarantee the (αf /2)(1-e-αf )- approximation ratio in polynomial running time.

In real-world applications of subset selection, the budget B on the cost constraint is, however, not fixed, but may change over time, reflecting the change of resources. For examples, in influence maximization, more market investment will make B increase; in sensor placement, some installed sensors may not work due to aging and thus B decreases. A natural question is then whether the generalized greedy algorithm, POMC and EAMC can adapt their solutions quickly when the budget B changes dynamically.

The answer is unfortunately negative. For the generalized greedy algorithm, Roostapour et al. [2019] have constructed instances where the approximation ratios are arbitrarily bad. Though POMC can maintain the (αf /2)(1 - e-αf )- approximation ratio, the required running time depends on the population size, which is unbounded and may be even exponential [Roostapour et al., 2019]. EAMC uses a surrogate objective depending on B, and thus, the change of B leads to the change on the objective, making the found solutions probably unhelpful for solving the problem with a new B.

In this paper, we propose a new algorithm FPOMC for subset selection with dynamic cost constraints, i.e., dynamically changing B. As the generalized greedy algorithm runs efficiently but cannot guarantee the approximation ratio, while POMC maintains the approximation ratio but cannot guarantee the polynomial running time, the idea of FPOMC is naturally to combine their merits. In particular, FPOMC is modified from POMC by introducing a greedy selection strategy. POMC uses the uniform selection strategy, i.e., selects a solution from the population uniformly at random, for mutation, while FPOMC first selects a subset size uniformly at random, and then selects a specific solution with this size greedily from the population. We prove that when the budget B decreases, FPOMC has already achieved the (αf /2)(1-e-αf )- approximation ratio; when B increases to B′ , FPOMC can regain the (αf/2)(1 - e-αf )-approximation ratio using at most O(nKB′(KB′ - KB)) expected running time, where KB and KB′ denote the largest size of a subset satisfying the two constraints c(X) ≤ B and c(X) ≤ B′ , respectively.

2 Subset Selection with Cost Constraints

Let R and R+ denote the set of reals and non-negative reals, respectively. Let V = {v1, v2, . . . , vn} denote a ground set. A set function f : 2V →R is monotone if

A set function f is submodular if

implying the diminishing returns property [Nemhauser et al., 1978]. The submodularity ratio

is used to characterize the closeness of a general set function f to submodularity [Zhang and Vorobeychik, 2016; Qian et al., 2018]. When f satisfies the monotone property, we have 0 ≤ αf ≤ 1, and f is submodular iff αf = 1.

As presented in Definition 1, the subset selection problem with static cost constraints is to maximize a monotone objective function f such that a monotone cost function c is no larger than a budget B. We assume w.l.o.g. that monotone functions are normalized, i.e., f(∅) = 0 and c(∅) = 0.

Definition 1 (Subset Selection with Static Cost Constraints). Given a monotone objective function f : 2V → R+, a monotone cost function c : 2V →R+ and a budget B, to find

Because the cost function c is hard to be computed exactly in some real-world applications [Zhang and Vorobeychik, 2016; Qian et al., 2017], we assume that only an ψ(n)- approximation ˆ c can be obtained, where

This general problem has many applications such as influence maximization [Kempe et al., 2003] and sensor placement [Krause et al., 2008]. Influence maximization is to select a subset of users in social networks such that they can influence the most number of users in expectation, which often appears in advertisement marketing. Sensor placement is to select a few places from all candidate ones to install sensors such that the remaining uncertainty of the environment is mostly reduced, which often appears in fire detection and water contamination detection.

Note that the problem in Definition 1 assumes a fixed budget B. However, in real-world scenarios, the resources often change over time, and thus the budget B may be not fixed, but change dynamically. For examples, in the application of influence maximization, a company may increase or decrease his investment according to the market situation; in the application of sensor placement, some installed sensors may fail due to aging, or some new sensors may be purchased for placement. In both cases, the budget B will change. In this paper, we focus on the subset selection problem with dynamic cost constraints, presented as follows.

Definition 2 (Subset Selection with Dynamic Cost Constraints). Given a monotone objective function f : 2V → R+, a monotone cost function c : 2V → R+ and a sequence of changes on the budget B, to find a subset optimizing Eq. (3) for each new B.

Note that after each change of the budget B, we can view the problem as a static problem with the new budget, and run any algorithm from scratch, which, however, may lead to a long running time and a significantly different solution. As in [Bossek et al., 2019; Doskoˇc et al., 2020; Assimi et al., 2020; Do and Neumann, 2021], the main focus of this paper is the ability of algorithms adapting to the changes of B. That is, we concern the running time of an algorithm until regaining the φ-approximation ratio w.r.t. the new budget B′ , when starting from the solutions having a desired approximation ratio of φ w.r.t. the old budget B.

3 Previous Algorithms

In this section, we introduce three state-of-the-art algorithms for the subset selection problem with cost constraints, and show their approximation performances.

3.1 The Generalized Greedy Algorithm

The generalized greedy algorithm [Zhang and Vorobeychik, 2016] iteratively selects one itemmaximizing the ratio of the marginal gain on f and ˆ c. After examining all items, the algorithm compares the found subset with the best single item, and returns the better one. Let

where αc and αˆ c are the submodularity ratios of the cost function c and its approximation ˆ c in Eq. (4), respectively, κc = 1-minv∈V :c({v})>0 c(V )-c(V \{v}) c({v}) is the total curvature of c, and KB = max{|X| | c(X) ≤ B}, i.e., the largest size of a subset satisfying the constraint. ˜X is actually an optimal solution of Eq. (3) with a slightly smaller budget constraint, because αˆ c(1+α2c (KB-1)(1-κc)) ψ(n)KB ≤ 1, where the inequality holds by 1 - κc ≤ 1/αc, 0 ≤ αˆ c, αc ≤ 1 and ψ(n) ≥ 1. Theorem 1 shows that the generalized greedy algorithm can obtain the approximation ratio of (αf /2)(1 - e-αf ) w.r.t. f( ˜X).

Theorem 1. [Qian et al., 2017] For subset selection with static cost constraints in Definition 1, the generalized greedy algorithm finds a subset X ⊆ V with

To handle the dynamic situation where the budget B changes over time, Roostapour et al. [2019] introduced a natural adaptive version of the generalized greedy algorithm. When B increases, the algorithm continues to add items greedily; when B decreases, it iteratively deletes one item which minimizes the ratio of the marginal loss on f and ˆ c. However, this adaptive algorithm cannot adapt the solutions well, and the obtained approximation ratio can be arbitrarily bad, as shown in the following theorem.

Theorem 2. [Roostapour et al., 2019] For subset selection with dynamic cost constraints in Definition 2, there exist instances of increasing B and decreasing B such that the approximation ratios achieved by the adaptive generalized greedy algorithm are O(1/n) and O(1/√n), respectively.

3.2 The POMCAlgorithm

Qian et al. [2017] proposed an approach based on Pareto Optimization [Friedrich and Neumann, 2015; Qian et al., 2015] for maximizing a Monotone function with a monotone Cost constraint, called POMC, which can use more time to find better solutions. It represents a subset X ⊆ V by a Boolean vector x ∈ {0, 1}n , where the i-th bit xi = 1 iff vi ∈ X. POMC tries to maximize the objective function f and minimize the approximate cost function ˆ c simultaneously, by reformulating the original problem Eq. (3) as a bi-objective maximization problem

The solutions violating the constraint (i.e., with ˆ c(X) > B) are excluded by setting their f1 values to -∞. Note that the idea of bi-objective reformulation has been used to tackle hard problems, e.g., covering [Friedrich et al., 2010] and balancing [Chica et al., 2010] problems.

After the bi-objective transformation, POMC employs a simple multi-objective EA, i.e., GSEMO [Laumanns et al., 2004; Qian et al., 2019], to solve the bi-objective problem. It starts from the empty set 0n . In each iteration of POMC, a parent solution x is selected from the population P uniformly at random, and used to generate an offspring solution x′ by flipping each bit with probability 1/n; x′ is then used to update P by domination-based comparison as presented in Definition 3. After terminated, POMC returns the solution with the largest f value in P.

Definition 3 (Domination). For two solutions x and x′ ,

• x weakly dominates x′ , denoted as x ⪰ x′ , if f1(x) ≥ f1(x′ ) ∧ f2(x) ≥ f2(x′ );
• x dominates x′ , denoted as x ≻ x′ , if x ⪰ x′ and either f1(x) > f1(x′ ) or f2(x) > f2(x′ );
• they are incomparable if neither x ⪰ x′ nor x′ ⪰ x.

Let Pmax denote the largest size of the population P during the running of POMC, and δˆ c = min{ˆ c(X ∪ {v}) - ˆ c(X) | X ⊆ V, v /∈ X} denote the minimum increment on ˆ c by adding a single item. The following two theorems show that POMC can achieve the approximation ratio of (αf/2)(1 - e-αf ) for a fixed budget, and can also regain this approximation ratio when the budget increases.

Theorem 3. [Qian et al., 2017] For subset selection with static cost constraints in Definition 1, POMC using E[T] ≤ enBPmax/δˆ c finds a subset X ⊆ V with

Theorem 4. [Roostapour et al., 2019] For subset selection with dynamic cost constraints in Definition 2, when B is increased to B′ , POMC using T = rn(B′ -B)Pmax/δˆ c can regain the approximation ratio of (αf /2)(1-e-αf ) with probability Ω(1), where r ≥ 8e + 1 is a constant.

However, for either static or dynamic cases, the running time of POMC depends on Pmax, B (or B′ -B) and 1/δˆ c, all of which may be exponentially large w.r.t. n, resulting in the exponential running time of POMC.

3.3 The EAMCAlgorithm

Bian et al. [2020] proposed a simple EA for maximizing a Monotone function with a monotone Cost constraint, called EAMC. It tries to maximize a surrogate objective

which considers both the original objective f and the cost ˆ c, where | · | denotes the number of 1-bits of a vector. EAMC maintains a solution set bin(i) for each subset size i, which contains at most two solutions, one with the largest g value (denoted as ui ) and the other with the largest f value (denoted as vi ) generated-so-far. In each iteration, it generates an offspring solution x′ as same as POMC. If x′ satisfies the constraint, bin(|x′ |) will be updated by comparing x′ with u|x′ | and v|x′ | . After terminated, EAMC returns the solution with the largest f value in the population, which must satisfy the constraint.

Theorem 5. [Bian et al., 2020] For subset selection with static cost constraints in Definition 1, EAMC using E[T] ≤ 2en2 (n + 1) finds a subset X ⊆ V with

The above theorem shows that for a fixed budget, EAMC can achieve the (αf/2)(1 - e-αf )-approximation ratio in O(n3 ) expected running time. However, in dynamic environments, the budget B can change to B′ . Note that the solutions kept in the population are decided by the g function defined in Eq. (7), which relies on B. After B changes, g cannot characterize the new problem well, and thus the solutions may perform bad for B′ .

4 The FPOMCAlgorithm

In this section, we propose the Fast Pareto Optimization algorithm for maximizing a Monotone function with a monotone Cost constraint, called FPOMC.

FPOMC also tries to solve the reformulated bi-objective maximization problem Eq. (6). It is actually modified from POMC by introducing a greedy selection strategy. For POMC, the population size is unbounded and the selection is uniform. Thus, it is very likely to select a "bad" solution, which may decrease the efficiency of the algorithm. Inspired from the generalized greedy algorithm, we define a function h to estimate the goodness of a solution in selection, and the solution with the largest h value is selected with a high probability. This selection mechanism can guide the search direction efficiently and accelerate the optimization procedure.

To be specific, the population P is divided into subpopulations P0, . . . , Pn, where Pi = {x ∈ P | |x| = i} denotes the set of solutions with size i in P. In each iteration, FPOMC first selects a subset size i (which has corresponding solutions in the population) uniformly at random, and then selects a solution having the largest h value from Pi with probability 1/2. The function hz(x) is defined as

where x is a solution in Pi, z is a reference point, and C is a large enough number. Intuitively, hz(x) measures the goodness of x by the marginal gain on f and ˆ c w.r.t. a reference point z, and FPOMC selects a solution greedily, i.e., having the largest h value. For each subset size i, FPOMC maintains a reference point, denoted by xi , which is updated adaptively during the running of the algorithm.

The procedure of FPOMC is described in Algorithm 1. Starting from the empty set 0n (line 1), it repeatedly improves the solutions in each subpopulation Pi (lines 2-22). In each iteration, a solution in P is selected (line 3) according to the SELECT subroutine in Algorithm 2. Then, a solution x′ is generated by randomly flipping bits of x (line 4), which is used to update the population Pj (line 7) and the reference point xj (lines 8-13), respectively. Note that if xj is updated (line 13), a local search (LS) subroutine in Algorithm 3 is employed to quickly exploit the new solution xj (line 14), and the generated solution y will be used to update Pj+1 (lines 15-17). After T iterations, the solution with the largest f value in the population P is output (line 23).

The SELECT subroutine in Algorithm 2 selects a nonempty Pi randomly, and returns a solution x ∈ S with probability 1/2, where S denotes the set of solutions in Pi such that hz(·) is maximized. Note that if xi exists and is contained in S, it is preferred than other solutions in S. To determine S, the reference point z is selected to be the existing xk with the largest k smaller than i. With the other probability of 1/2, a solution in Pi \ S is selected uniformly at random.

The LS subroutine in Algorithm 3 returns a solution y by adding an item into x, such that hx(y) is maximized. By Eq. (8), y is actually generated by adding an item with the largest ratio of the marginal gain on f and ˆ c w.r.t. x.

Algorithm 1 FPOMC Algorithm

Input: a monotone objective function f , a monotone approx-

imate cost function ˆ c, and a budget B Parameter: the number T of iterations Output: a solution x ∈ {0, 1}n with ˆ c(x) ≤ B Process: 1: Let x = x0 = 0n , P = {x} and t = 0; 2: while t < T do 3: x = SELECT(P); 4: Generate x′ by flipping each bit of x with prob. 1/n; 5: Let j = |x′ |; 6: if 0 < ˆ c(x′ ) ≤ B and ∄s ∈ Pj such that s ≻ x′ then 7: Pj = (Pj \ {s ∈ Pj | x′ ⪰ s}) ∪ {x′ }; 8: if xj doesn't exist then 9: Let xj = x′ 10: else 11: Let z = xk , where k is the largest integer such that k < j and xk exists; 12: if hz(x′ ) ≥ max{hz(xj ), hz(LS(z))} then 13: xj = x′ ; 14: y = LS(xj ); 15: if ˆ c(y)≤B and ∄s∈Pj+1 such thats≻y then 16: Pj+1 = (Pj+1 \{s ∈ Pj+1 | y ⪰ s})∪{y} 17: end if 18: end if 19: end if 20: end if 21: t = t +1 22: end while 23: return argmaxx∈P f(x)

5 Theoretical Analysis

In this section, we prove the general approximation bound of FPOMC in Theorem 6, implying that FPOMC can achieve the best known polynomial-time approximation guarantee, i.e., (αf /2)(1-e-αf ). We also prove that when the budget B decreases, FPOMC has already achieved the (αf /2)(1-e-αf )- approximation ratio (Theorem 7); when B increases to B′ , FPOMC can regain the (αf /2)(1 - e-αf )-approximation ratio in at most O(nKB′(KB′ -KB)) expected running time (Theorem 8), where KB and KB′ denote the largest size of a subset satisfying c(X) ≤ B and c(X) ≤ B′ , respectively.

The proof of Theorem 6 relies on Lemma 1, which intuitively means that for any subset, the inclusion of a specific item can improve f by at least a quantity proportional to the current distance to the optimum. As in [Zhang and Vorobeychik, 2016; Qian et al., 2017], we assume that ∀v ∈ V : ˆ c({v}) ≤ B and δˆ c defined in Section 3.2 is larger than 0.

Theorem 6. For the problem in Definition 1, FPOMC using E[T ] = O(n2KB) finds a subset X ⊆ V with

where f( ˜X) is defined in Eq. (5).

Algorithm 2 SELECT(P): Subroutine of FPOMC

Input: the population P

Output: a solution in P for mutation

Process:

• 1: Choose a nonempty Pi uniformly at random;
• 2: Let z = xk , where k is the largest integer such that k < i and xk exists;
• 3: Let S = {x | x ∈ argmaxx∈Pi hz(x)};
• 4: if xi ∈ S then
• 5: Let s = xi
• 6: else
• 7: Let s = a solution uniformly selected from S
• 8: end if
• 9: Let x = s or a solution uniformly selected from Pi \ S, with equal probability, i.e., 1/2
• 10: return x

Algorithm 3 LS(x): Subroutine of FPOMC

Input: the solution x

Output: a solution with size |x| + 1

Process:

• 1: Let y = x;
• 2: for i = 1, 2, . . . , n do
• 3: if xi = 0 then
• 4: Let s = x, and set its i-th bit to 1, i.e., si = 1;
• 5: if hx(s) ≥ hx(y) then

6:

y = s

• 7: end if
• 8: end if
• 9: end for
• 10: return y

Proof. The theorem is proved by analyzing the increase of Jmax, which is defined as the maximal J such that ∀1 ≤ i ≤ J, the following two conditions hold:

• C1: ∃xi-1 such that D(xi-1 ) holds;

We first show that Jmax ≥ 1 after at most en(KB + 1) expected number of iterations. By lines 9 and 13 of Algorithm 1, x0 can only be replaced by a solution with size 0, thus x0 is always 0n . Then we have f(x0 ) = (1 - e-αf ˆ c(0n )/B ) · f( ˜X) = 0, which implies that condition C1 holds for i = 1. By the update procedure of FPOMC, 0n will always be kept in P. In each iteration, 0n will be selected for mutation with probability at least 1/(KB + 1) by line 3 of Algorithm 1. Flipping a specific 0-bit of 0n (i.e., adding a specific item) can generate a new solution x′ with |x′ | = 1 such that hx0(x′ ) = hx0(x0 ∪ {v0 ∗ }). Thus, in each iteration, x′ can be generated with probability at least 1 KB+1 · 1n (1 - 1n )n-1 ≥ 1 en(KB+1) , implying that it needs at most en(KB + 1) expected number of iterations to generate x′ . If x′ is added into P, condition C2 holds for i = 1; otherwise, there must exist a solution s ∈ P1 such that f(s) ≥ f(x′ ) and ˆ c(s) ≤ ˆ c(x′ ), implying that hx0 (s) ≥ hx0 (x′ ) = hx0 (x0 ∪ {v0 ∗ }), and thus condition C2 has already hold. Thus, after en(KB + 1) expected number of iterations, Jmax ≥ 1.

Assume that currently Jmax = J, we now show that Jmax will not decrease. Assume that in some iteration t, a solution x′ with |x′ | = j, 1 ≤ j ≤ J - 1, is generated and added into Pj in line 7. We need to show that condition C1 holds for j + 1, and condition C2 holds for j and j + 1.

First we consider condition C1, i.e., D(xj ) holds. If xj is not replaced by x′ in line 13, C1 trivially holds. Thus, we only need to consider that xj is replaced. By line 12, we have hxj-1(x′ ) ≥ hxj-1(LS(xj-1 )). Note that xj is replaced by x′ , we have

implying hxj-1(xj ) ≥ 0 by Eq. (9). Next, we consider two cases for ˆ c(xj ) - ˆ c(xj-1 ). (1) ˆ c(xj ) - ˆ c(xj-1 ) ≤ 0, then by Eq. (8), hxj-1(xj ) = (f(xj ) - f(xj-1 )) · C + ˆ c(xj-1 ) - ˆ c(xj ) ≥ 0. Because C is large enough, we have f(xj ) ≥ f(xj-1 ). Thus,

where the first inequality is by Eqs. (8) and (9), and the second inequality is by Lemma 1. Thus,

where the first inequality holds by Eq. (11) and the definition of Jmax, and the second inequality holds by ∀r ∈ R : 1 - r ≤ e-r . Combining cases (1) and (2), D(xj ) holds, i.e., condition C1 holds for j + 1.

Now we consider condition C2 for j. Before x′ is added into Pj, there must exist a solution s ∈ Pj such that hxj-1(s) ≥ hxj-1(xj-1 ∪ {vj-1 ∗ }) according to the definition of Jmax. If s is not deleted, condition C2 trivially holds for j. Thus, we only need to consider that s is deleted from Pj in line 7, implying that f(x′ ) ≥ f(s) and ˆ c(x′ ) ≤ ˆ c(s). By Eq. (10), we have hxj-1(s) ≥ 0, implying f(s) ≥ f(xj-1 )

according to Eq. (8). By classification on ˆ c(xj-1 ), we will show that

(1) ˆ c(xj-1 ) < ˆ c(x′ ) ≤ ˆ c(s). Then, by Eq. (8), hxj-1(x′ ) = f (x′ )-f (xj-1 ) ˆ c(x′ )-ˆ c(xj-1 ) ≥ f(s)-f(xj-1 ) ˆ c(s)-ˆ c(xj-1 ) = hxj-1(s). (2) ˆ c(x′ ) ≤ ˆ c(xj-1 ) < ˆ c(s). Then, by Eq. (8), hxj-1(x′ ) = (f (x′ ) - f (xj-1 )) · C + ˆ c(xj-1 ) - ˆ c(x′ ) > f(s)-f(xj-1 ) ˆ c(s)-ˆ c(xj-1 ) = hxj-1(s), where the inequality holds for large enough C. (3) ˆ c(x′ ) ≤ ˆ c(s) ≤ ˆ c(xj-1 ). Then, by Eq. (8), hxj-1(x′ ) = (f(x′ )-f(xj-1 ))·C+ˆ c(xj-1 )-ˆ c(x′ ) ≥ (f (s)-f (xj-1 ))· C + ˆ c(xj-1 ) - ˆ c(s) = hxj-1 (s).

Combining the three cases, we have proved Eq. (12), implying that condition C2 holds for j.

If xj is updated by x′ in line 13, the LS subroutine will generate a solution y with |y| = j + 1 such that hxj (y) = hxj (xj ∪ {vj∗}). If y is added into Pj+1, condition C2 holds for j +1; otherwise, there must exist a solution s ∈ Pj+1 that dominates y. Then, similar to the analysis of Eq. (12), we have hxj (s) ≥ hxj (y) = hxj (xj ∪ {vj∗}). Thus, condition C2 also holds for j + 1.

By far, we have shown that Jmax will not decrease when the newly generated solution x′ satisfies 1 ≤ |x′ | = j ≤ J - 1. When j = J, we only need to consider condition C2 for j, and the proof is similar to the analysis of Eq. (12). Thus, Jmax will always not decrease.

Next we consider the increase of Jmax. Let x∗ = argmaxx∈PJ hxJ-1(x). By the definition of Jmax, we have hxJ-1 (x∗ ) ≥hxJ-1 (xJ-1∪{vJ-1 ∗ }). We consider two cases: (1) xJ exists and hxJ-1(xJ ) = hxJ-1(x∗ ), then similar to the analysis after Eq. (9), D(xJ ) holds, i.e., condition C1 holds for J + 1. In each iteration, xJ will be selected with probability at least 1/(2(KB + 1)) by line 3. The probability that no bits of xJ are flipped in line 4 is (1-1/n)n ≥ (1-1/n) · 1/e, and the generated solution will be added into PJ in line 7 and used to update xJ in line 13. Then, the LS subroutine will generate a solution y such that hxJ (y) = hxJ (xJ ∪ {vJ ∗ }).

If ˆ c(y) ≤ B, y will be used to update PJ+1 in line 16. If y is not added into PJ+1, there must exist a solution s ∈ PJ+1 that dominates y. Similar to the analysis of Eq. (12), we have hxJ (s) ≥ hxJ (y) = hxJ (xJ ∪ {vJ ∗ }), implying that condition C2 holds for J + 1. If y is added into PJ+1, condition C2 also holds for J + 1. Thus, Jmax can increase by 1.

If ˆ c(y) > B, similar to the analysis after Eq. (9), D(y) holds, implying f(y) ≥ (1 - e-αf ) · f( ˜X). Let u ∈ arg maxv∈V :ˆ c({v})≤B f({v}). We have

where the first inequality holds by Eq. (2), and the last holds by αf ∈ [0, 1]. In each iteration, u can be generated by selecting 0n and flipping a specific 0-bit, occurring with probability at least 1/(en(KB + 1)). Thus, u can be generated in at most en(KB + 1) expected number of iterations. According to the updating procedure of P1 in lines 7 and 16, we know that once u is generated, P will always contain a solution u′ ∈ P1 with f(u′ ) ≥ f(u). Thus, FPOMC finds a solution with the f value at least max{f(xJ ), f(u)} ≥ (αf/2)f(y) ≥ (αf/2)(1 - e-αf ) · f( ˜X). i.e., the desired approximate solution has been found.

(2) xJ exists and hxJ-1(xJ ) < hxJ-1(x∗ ), or xJ doesn't exist. The proof is similar to that of case (1), and the only difference is that x∗ instead of xJ is selected for mutation.

Combining the two cases, Jmax can increase by 1, i.e., conditions C1 and C2 hold for J + 1, in O(KB) iterations, or it has found a solution x with f (x) ≥ (αf /2)(1-e-αf )·f ( ˜X).

Finally, we examine the total expected number of iterations. Note that Jmax can increase to at most KB, because a solution with size larger than KB will violate the constraint. To make Jmax ≥ 1, the expected number of iterations is at most en(KB + 1); to increase Jmax from 1 to KB, the expected number of iterations is at most O(KB) · KB = O(K2B ); to generate u, the expected number of iterations is at most en(KB +1). Thus, the total expected number of iterations is O(nKB). Note that in each iteration, FPOMC needs to evaluate the objective value at most 2n + 1 times (i.e., the cost of evaluating x′ and two LS subroutines), implying that the total expected running time is O(n2KB).

Theorem 7. For the problem in Definition 2, assume FPOMC achieves a (αf/2)(1 - e-αf )-approximation ratio, when B decreases to B′ , FPOMC has already achieved the (αf /2)(1 - e-αf )-approximation ratio for the new problem.

Proof. The result can be derived from the proof of Theorem 6, because B can be replaced by B′ directly.

Theorem 8. For the problem in Definition 2, assume FPOMC achieves a (αf/2)(1 - e-αf )-approximation ratio, when B increases to B′ , FPOMC using E[T ] =O(nKB′ (KB′ -KB)) can regain the (αf /2)(1 - e-αf )-approximation ratio.

Proof. Note that FPOMC has run O(nKB) expected number of iterations, to achieve the (αf/2)(1-e-αf )-approximation ratio for the problem with budget B. For the problem with budget B′ , the B in the proof of Theorem 6 can be replaced by B′ directly, and after O(nKB) expected number of iterations, Jmax has increased to KB. To achieve the desired approximation guarantee, it is sufficient to continue increasing Jmax to KB′ , whose expected number of iterations is O(KB′(KB′ - KB)). Thus, the expected running time to regain the (αf/2)(1 - e-αf )-approximation ratio is O(nKB′ (KB′ - KB)).

6 Conclusion

This paper proposes a new algorithm FPOMC for subset selection with dynamic cost constraints. When the budget on the constraint changes dynamically, FPOMC can maintain the best known approximation ratio of (αf/2)(1 - e-αf ) efficiently, while previous algorithms either achieve arbitrarily bad approximation ratios or require a long running time to maintain this approximation ratio. FPOMC has shown its superiority theoretically, and it is expected to study the empirical performance of FPOMC in the future.