# dynamic_nonmonotone_submodular_maximization__140fed76.pdf

Dynamic Non-monotone Submodular Maximization

Kiarash Banihashem

kiarash@umd.edu University of Maryland

Leyla Biabani

l.biabani@tue.nl TU Eindhoven

Samira Goudarzi

samirag@umd.edu University of Maryland

Mohammad Taghi Hajiaghayi

hajiagha@cs.umd.edu University of Maryland

Peyman Jabbarzade

peymanj@umd.edu University of Maryland

Morteza Monemizadeh

m.monemizadeh@tue.nl TU Eindhoven

Maximizing submodular functions has been increasingly used in many applications of machine learning, such as data summarization, recommendation systems, and feature selection. Moreover, there has been a growing interest in both submodular maximization and dynamic algorithms. In 2020, Monemizadeh [46] and Lattanzi, Mitrovic, Norouzi-Fard, Tarnawski, and Zadimoghaddam [40] initiated developing dynamic algorithms for the monotone submodular maximization problem under the cardinality constraint k. In 2022, Chen and Peng [15] studied the complexity of this problem and raised an important open question: "Can we extend [fully dynamic] results (algorithm or hardness) to non-monotone submodular maximization?". We affirmatively answer their question by demonstrating a reduction from maximizing a non-monotone submodular function under the cardinality constraint k to maximizing a monotone submodular function under the same constraint. Through this reduction, we obtain the first dynamic algorithms solving the non-monotone submodular maximization problem under the cardinality constraint k. We ve derived two algorithms, both maintaining an (8 + ϵ)-approximate of the solution. The first algorithm requires O(ϵ 3k3 log3(n) log(k)) oracle queries per update, while the second one requires O(ϵ 1k2 log3(k)). Furthermore, we showcase the benefits of our dynamic algorithm for video summarization and max-cut problems on several real-world data sets.

1 Introduction

Submodular functions are powerful tools for solving real-world problems as they provide a theoretical framework for modeling the famous diminishing returns [30] phenomenon arising in a variety of practical settings. Many theoretical problems such as those involving graph cuts, entropy-based clustering, coverage functions, and mutual information can be cast in the submodular maximization framework. As a result, submodular functions have been increasingly used in many applications of machine learning such as data summarization [52, 51, 50], feature selection [17, 19, 18, 38], and recommendation systems [24]. These applications include both the monotone and non-monotone versions of the maximization of submodular functions.

Applications of non-monotone submodular maximization. The general problem of nonmonotone submodular maximization has been studied extensively in [27, 12, 11, 43, 5, 47]. This

equal contribution Department of Computer Science, University of Maryland, College Park, MD, USA. Department of Mathematics and Computer Science, Eindhoven University of Technology, the Netherlands.

37th Conference on Neural Information Processing Systems (Neur IPS 2023).

problem has numerous applications in video summarization, movie recommendation [43], and revenue maximization in viral marketing [35]4. An important application of this problem appears in maximizing the difference between a monotone submodular function and a linear function that penalizes the addition of more elements to the set (e.g., the coverage and diversity trade-off). An illustrative example of this application is the maximum facility location in which we want to open a subset of facilities and maximize the total profit from served clients plus the cost of facilities we did not open [21]. Another important application occurs when expressing learning problems such as feature selection using weakly submodular functions [17, 38, 25, 49].

Our contribution. In this paper, we consider the non-monotone submodular maximization problem under cardinality constraint k in the fully dynamic setting. In this model, we have a universal ground set V . At any time t, ground set Vt V is the set of elements that are inserted but not deleted after their last insertion till time t. More formally, we assume that there is a sequence of updates such that each update either inserts an element to Vt 1 or deletes an element from Vt 1 to form Vt.

We assume that there is a (non-monotone) submodular function f that is defined over the universal ground set V . Our goal is to maintain, at each point in time, a set of size at most k whose submodular value is maximum among any subset of Vt of size at most k.

Since calculating such a set is known to be NP-hard [27] even in the offline setting (where you get all the items at the same time), we focus on providing algorithms with provable approximation guarantees, while maintaining fast update time. This is challenging as elements may be inserted or deleted, possibly in an adversarial order. While several dynamic algorithms exist for monotone submodular maximization, non-monotone submodular maximization is a considerably more challenging problem as adding elements to a set may decrease its value.

In STOC 2022, Chen and Peng [15] raised the following open question:

Open problem: Can we extend [fully dynamic] results (algorithm or hardness) to non-monotone submodular maximization?

In this paper, we answer their question affirmatively by providing the first dynamic algorithms for non-monotone submodular maximization.

To emphasize the significance of our result, it should be considered that although monotone submodular maximization under cardinality constraint has a tight e e 1 approximation algorithm in the offline mode and nearly tight (2 + e) approximation algorithms for both streaming and dynamic settings, there is a hardness result for the non-monotone version stating that it is impossible to obtain a 2.04 (i.e., 0.491) approximation algorithm for this problem even in the offline setting[31], and to the best of our knowledge, the current state of the art algorithms for this problem have 2.6 and 3.6 (i.e., 0.385 and 0.2779) approximation guarantees for offline [10] and streaming settings [2], respectively.

We obtain our result, by proposing a general reduction from the problem of dynamically maintaining a non-monotone submodular function under cardinality constraint k to developing a dynamic thresholding algorithm for maximizing monotone submodular functions under the same constraint. We first define τ-thresholding dynamic algorithms that we use in our reduction. Definition 1.1 (τ-Thresholding Dynamic Algorithm). Let τ > 0 be a parameter. We say a dynamic algorithm is τ-thresholding if at any time t of sequence Ξ, it reports a set St Vt of size at most k such that

Property 1: either a) St has k elements and f(St) kτ, or b) St has less than k elements and for any v Vt \ St, the marginal gain (v|St) < τ.

Property 2: The number of elements changed in any update, i.e, |St+1\St| + |St\St+1|, is not more than the number of queries made by the algorithm during the update.

In the above definition, the first property reflects the main intuition of threshold-based algorithms, while the last property is a technical condition required in our analysis. It s worth noting that the thresholding technique has been used widely for optimizing submodular functions [46, 41, 26, 40, 16]. We next state our main result, which is a general reduction.

4The problem of selecting a subset of people in a social network to maximize their influence in a viral marketing campaign can be modeled as a constrained submodular maximization problem. When we introduce a cost, then the influence minus the cost is modeled as non-monotone submodular maximization problems [9, 8, 34].

Theorem 1.2 (Reduction Metatheorem). Suppose that f : 2V R 0 is a (possibly non-monotone) submodular function defined on subsets of a ground set V and let k N be a parameter.

Assume that for any given value of τ, there exists a τ-thresholding dynamic algorithm with an expected (amortized) O(g(n, k)) oracle queries per update. Then, there exist the following dynamic algorithms:

A dynamic algorithm with an approximation guarantee of (8 + ε) using an expected (amortized) O(k + min(k, g(n, k)) g(n, k) ε 1 log(k)) oracle queries per update.

A dynamic algorithm maintaining a (10 + ε)-approximate solution of the optimal value of f using an expected (amortized) O(min(k, g(n, k)) g(n, k) ε 1 log(k)) oracle calls per update.

In [46], Monemizadeh developed a dynamic algorithm for monotone submodular maximization under cardinality constraint k, which requires an amortized O(ε 2k2 log3(n)) number of oracle queries per update. Interestingly, in the appendix, we show that this algorithm is indeed τ-thresholding (for any given τ). Now, if we use this τ-thresholding dynamic algorithm inside our reduction Metatheorem 1.2, we obtain a dynamic algorithm that maintains a (8 + ε)-approximate solution using an expected amortized O(ε 3k3 log3(n) log(k)) oracle queries per update.

The recent paper [6] of Banihashem, Biabani, Goudarzi, Hajiaghayi, Jabbarzade, and Monemizadeh develops a new dynamic algorithm for monotone submodular maximization under cardinality constraint k, which uses an expected O(ε 1k log2(k)) number of oracle queries per update. A similar proof shows that this new algorithm is τ-thresholding as well. We have provided its pseudocode and a detailed explanation on why this algorithm is indeed τ-thresholding in the appendix. By exploiting this algorithm in our Reduction Metatheorem 1.2, we can reduce the number of oracle queries mentioned to an expected number of O(ε 2k2 log3(k)) per update.

The second result in Theorem 1.2 is also of interest as it can be used to devise a dynamic algorithm for non-monotone submodular maximization with polylogarithmic query complexity if one can provide a τ-thresholding dynamic algorithm for maximizing monotone submodular functions (under the cardinality constraint k) with polylogarithmic query complexity.

1.1 Preliminaries

Submodular maximization. Let V be a ground set of elements. We say a function f : 2V R 0 is a submodular function if for any A, B V , f(A) + f(B) f(A B) + f(A B). Equivalently, f is a submodular function if for any subsets A B V and for any element e V \B, it holds that f(A {e}) f(A) f(B {e}) f(B) . We define (e|A) := f(A {e}) f(A) the marginal gain of adding the element e to set A. Similarly, we define (B|A) := f(A B) f(A) for any sets A, B V . Function f is monotone if f(A) f(B) holds for any A B V , and it is nonmonotone if it is not necessarily the case. In the submodular maximization problem under cardinality constraint k, we seek to compute a set S such that |S | k and f(S ) = max|S| k f(S), where f is a submodular function and k N is a given parameter.

Query access model. Similar to recent dynamic works [40, 15], we assume the access to a submodular function f is given by an oracle. The oracle allows set queries such that for every subset A V , one can query the value f(A). In this query access model, the marginal gain f(e|A) .= f(A {e}) f(A) for every subset A V and an element e V \A, can be computed using two set queries. To do so, we first query f(A {e}) and then f(A).

Dynamic model. Let Ξ be a sequence of inserts and deletes of an underlying universe V . We assume that f : 2V R 0 is a (possibly non-monotone) submodular function defined on subsets of the universe V . We define time t to be the tth update (i.e., insertion or deletion) of sequence Ξ. We let Ξt be the sub-sequence of updates from the beginning of sequence Ξ till time t and denote by Vt V the set of elements that are inserted but not deleted from the beginning of the sequence Ξ till any time t. That is, Vt is the current ground set of elements. We let OPTt = max S Vt:|S| k f(S).

Query complexity. The query complexity of a dynamic α-approximate algorithm is the number of oracle queries that the algorithm must make to compute a solution St with respect to ground set Vt

whose submodular value is an α-approximation of OPTt. That is, |St| k and f(St) α OPTt. Observe that the dynamic algorithm remembers every query it has made so far. Thus results of queries made in previous times may help find St in current time t.

Oblivious adversarial model. The dynamic algorithms that we develop in this paper are in the oblivious adversarial model as is common for analysis of randomized data structures such as universal hashing [13]. The model allows the adversary, who is aware of the submodular function f and the algorithm that is going to be used, to determine all the arrivals and departures of the elements in the ground set V . However, the adversary is unaware of the random bits used in the algorithm and so cannot choose updates adaptively in response to the randomly guided choices of the algorithm. Equivalently, we can suppose that the adversary prepares the full input (insertions and deletions) before the algorithm runs.

1.2 Related Work

Offline algorithms. The offline version of non-monotone submodular maximization was first studied by Feige, Mirrokni, and Vondrák in [27]. They studied unconstrained non-monotone submodular maximization and developed constant-factor approximation algorithms for this problem. In the offline query access model, they showed that a subset S chosen uniformly at random has a submodular value which is a 4-approximation of the optimal value for this problem. In addition, they also described two local search algorithms. The first uses f as the objective function, and provides 3-approximation and the second uses a noisy version of f as the objective function and achieves an improved approximation guarantee 2.5 for maximizing unconstrained non-monotone non-negative submodular functions. Interestingly, they showed (2 ε)-approximation for symmetric submodular functions would require an exponential number of queries for any fixed ε > 0.

Oveis Gharan and Vondrák [32] showed that an extension of the 2.5-approximation algorithm can be seen as simulated annealing method which provides an improved approximation of roughly 2.4. Later, Buchbinder, Feldman, Naor, and Schwartz [11] at FOCS 12, presented a randomized linear time algorithm achieving a tight approximation guarantee of 2 that matches the known hardness result of [27]. Bateni, Hajiaghayi, and Zadimoghaddam [9, 8] and Gupta, Roth, Schoenebeck, and Talwar [34] independently studied non-monotone submodular maximization subject to cardinality constraint k in the offline and secretary settings. In particular, Gupta et al. [34] obtained an offline 6.5-approximation for this problem.

All of the aforementioned approximation algorithms are offline, where the whole input is given in the beginning, whereas the need for real-time analysis of rapidly changing data streams motivates the study of this problem in settings such as the dynamic model that we study in this paper.

Streaming algorithms. The dynamic model that we study in this paper is closely related to the streaming model [3, 36]. However, the difference between these two models is that in the streaming model, we maintain a data structure using which we compute a solution at the end of the stream and so, the time to extract the solution is not important as we do it once. However, in the dynamic model, we need to maintain a solution after every update, thus, the update time of a dynamic algorithm should be as fast as possible.

The known streaming algorithms [44, 28, 29] work in the insertion-only streaming model and they do not support deletions as well as insertions. Indeed, there are streaming algorithms [37, 45] for the monotone submodular maximization problem that support deletions, but the space and the update time of these algorithms depend on the number of deletions which could be Ω(n), where n = |V | is the size of ground set V .

For monotone submodular maximization, Badanidiyuru, Mirzasoleiman, Karbasi, and Krause [4] proposed an insertion-only streaming algorithm with a (2+ε)-approximation guarantee under a cardinality constraint k. Chekuri, Gupta, and Quanrud [14] presented (insertion-only) streaming algorithms for maximizing monotone and non-monotone submodular functions subject to p-matchoid constraint5. Later, Mirzasoleiman, Jegelka, and Krause [44] and Feldman, Karbasi, and Kazemi [28] devel-

5For non-monotone submodular maximization subject to cardinality constraint k, Chekuri, Gupta, and Quanrud [14] claimed that they obtained 4.7-approximation algorithm. However, Alaluf, Ene, Feldman, Nguyen, and Suh [1] found an error in the proof of this approximation guarantee.

oped streaming algorithms with better approximation guarantees for maximizing a non-monotone function under a p-matchoid constraint. Currently, the best streaming algorithm for maximizing a non-monotone submodular function subject to a cardinality constraint is due to Alaluf, Ene, Feldman, Nguyen, and Suh [1] whose approximation guarantee is 3.6 + ε, improving the 5.8-approximation guarantee that was proposed by Feldman et al. [28].

Dynamic algorithms. At Neur IPS 2020, Lattanzi, Mitrovic, Norouzi-Fard, Tarnawski, and Zadimoghaddam [40] and Monemizadeh [46] initiated the study of submodular maximization in the dynamic model. They presented dynamic algorithms that maintain (2 + ε)-approximate solutions for maximizing a monotone submodular function subject to cardinality constraint k. Later, at STOC 2022, Chen and Peng [15] studied the complexity of this problem and they proved that developing a c-approximation dynamic algorithm for c < 2 is not possible unless we use a number of oracle queries polynomial in the size of ground set V . In 2023, Banihashem, Biabani, Goudarzi, Hajiaghayi, Jabbarzade, and Monemizadeh[7] developed an algorithm for monotone submodular maximization problem under cardinality constraint k using a polylogarithmic amortized update time. Concurrent works of Banihashem, Biabani, Goudarzi, Hajiaghayi, Jabbarzade, and Monemizadeh[6] and Duetting, Fusco, Lattanzi, Norouzi-Fard, and Zadimoghaddam[22] developed the first dynamic algorithms for monotone submodular maximization under a matroid constraint. Authors of [6] also improve the algorithm of [46] for monotone submodular maximization subject to cardinality constraint k. There are also studies on the dynamic model of influence maximization, which shares similarities with submodular maximization [48].

In this paper, for the first time, we study the generalized version of their problem by presenting an algorithm for maximizing the non-monotone submodular functions in the dynamic setting.

2 Dynamic algorithm

In this section, we explain the algorithm that we use in the reduction that we stated in Metatheorm 1.2. The pseudocode of our algorithm is given in Algorithm 1, Algorithm 2, and Algorithm 3.

Such reductions were previously proposed in the offline model by [34], and later works extended this idea to the streaming model [14, 44]. We develop a reduction in the dynamic model inspired by these works, though in our proof, we require a tighter analysis to obtain the approximation guarantee in our setting.

We consider an arbitrary time t of sequence Ξ where Vt is the set of elements inserted before time t, but not deleted after their last insertion. Let OPT t = max S Vt:|S| k f(S). For simplicity, we drop t from Vt and OPT t , when it is clear from the context.

In the following, we assume that the value of OPT is known. Although the exact value of OPT is unknown, we can maintain parallel runs of our dynamic algorithm for different guesses of the optimal value. By using (1 + ε )i, where i Z as our guesses for the optimal value, one of our guesses (1 + ε )-approximates the value of OPT . We show that the output of our algorithm satisfies the approximation guarantee in the run whose OPT (1 + ε )-approximates the value of OPT . Later, in the appendix, we show that it is enough to consider each element e only in runs i for which we have ε

k (1 + ε )i f(e) (1 + ε )i. This method increases the query complexity of our dynamic algorithm by only a factor of O(ε 1 log k).

Our approach for solving the non-monotone submodular maximization is to first run the thresholding algorithm with input set V to find a set S1 of at most k elements. Since f is non-monotone, subsets of S1 might have a higher submodular value than f(S1). Then, we use an α-approximation algorithm (for 0 < α 1) to choose a set S 1 S1 with guarantee E[f(S 1)] α max C S1 f(C). Next, we run the thresholding algorithm with the input set V \S1 and compute a set S2. At the end, we return set S = arg max C {S1,S 1,S2} f(C). Intuitively, for an optimal solution S , if f(S1 S ) is a good approximation of OPT, then f(S 1) is a good approximation of OPT. On the other hand, if both f(S1) and f(S1 S ) are small with respect to OPT, then we can ignore the elements of S1 and show that we can find a set S2 V \ S1 of size at most k whose submodular value is a good approximation of OPT. The following lemma proves that the submodular value of S is a reliable approximation of the optimal solution. The formal proof of this lemma can be found in Section 2.

Lemma 2.1 (Approximation Guarantee). Assuming that OPT [ OP T

1+ε , OPT], the expected submodular value of set S is E[f(S)] (1 O(ε )) OP T

Next, we explain the steps of our reduction in detail.

Let us first fix the threshold τ = OP T k(3+1/(2α)). Then, we fix a τ-thresholding dynamic algorithm (for example, [46] or [6]) and suppose we denote it by DYNAMICTHRESHOLDING. Before sequence Ξ of updates starts, we create two independent instances I1 and I2 of DYNAMICTHRESHOLDING. The first instance will maintain set S1 and the second instance will maintain set S2. For instance Ii where i {1, 2}, we consider the following subroutines:

INSERTIi(v): This subroutine inserts an element v to instance Ii.

DELETEIi(v): Invoking this subroutine will delete the element v from instance Ii.

EXTRACTIi: This subroutine returns the maintained set (of size at most k) of Ii.

Extracting S1. After the update at time t, first, we would like to set Z = S 1 {v} or Z = S 1 \{v}, if the update is the insertion of an element v or the deletion of an element v, respectively, where S 1 is the set S1 that instance I1 maintains just before this update. To find set S 1 , we just need to invoke subroutine EXTRACTI1. If the update is an insertion, we insert it into instance I1 using INSERTI1(v, τ), and if the update is a deletion, we delete v from both I1 and I2 using DELETEI1(v) and DELETEI2(v). We then invoke EXTRACTI1 once again to return set S1.

Extracting S 1. Buchbinder et al. [11] developed a method to extract a subset S 1 S1 whose submodular value is a good approximation of max C S1 f(C). In this algorithm, we start with two solutions and S1. The algorithm considers the elements (in arbitrary order) one at a time. For each element, it determines whether it should be added to the first solution or removed from the second solution. Thus, after a single pass over set S1, both solutions completely coincide, which is the solution that the algorithm outputs. They show that a (deterministic) greedy choice in each step obtains 3-approximation of the best solution in S1. However, if we combine this greedy choice with randomization, we can obtain a 2-approximate solution. Since we do a single pass over set S1, the number of oracle queries is O(|S1|).

The second algorithm that we can use to extract S 1 is a random sampling algorithm proposed by Feige et al. [27], which choose every element in S1 with probability 1/2. They show that this random sampling returns a set S 1 whose approximation factor is 1/4 of max C S1 f(C), and its number of oracle calls is O(1). We denote either of these two methods by SUBSETSELECTION.

Extracting S2. Next, we would like to update the set S2 that is maintained by instance I2. To do this, for every element u Z\S1, we add it to I2 using INSERTI2(u, τ), and for every element u S1\Z, we delete it from I2 using DELETEI2(u, τ). Finally, when I2 exactly includes all the current elements other than the ones in S1, we call subroutine EXTRACTI2 to return set S2.

Corollary 2.2. We obtain the (8 + ε) approximation guaranty stated in the Metatheorem 1.2 by using the local search method for our SUBSETSELECTION, and we get the (10 + ε) approximation guaranty by utilizing the random sampling method for our SUBSETSELECTION subroutine.

Proof. These are immediate results of Lemma 2.1, and α being 1

4 in the local search method and random sampling method, respectively.

Algorithm 1 Initialization(k, OPT)

1: τ OP T k(3+1/(2α)), where α is 1

4 based on the selection of algorithm for SUBSETSELECTION. 2: Instantiate two independent instances I1 and I2 of DYNAMICTHRESHOLDING for monotone submodular maximization under cardinality constraint k using τ

Algorithm 2 UPDATE(v)

1: Z EXTRACTI1 2: if UPDATE(v) is an insertion then 3: Invoke INSERTI1(v), Z Z {v} 4: else 5: Invoke DELETEI1(v), DELETEI2(v), Z Z \ {v} 6: S1 EXTRACTI1 7: S 1 SUBSETSELECTION(S1) 8: for u S1\Z do 9: DELETEI2(u) 10: for u Z\S1 do 11: INSERTI2(u) 12: S2 EXTRACTI2 13: Return arg max C {S1,S 1,S2} f(C)

Algorithm 3 SUBSETSELECTION(S)

1: function UNIFORMSUBSET(S) 2: T 3: for s S do 4: if Coin( 1

2) then With probability 1

2 5: T T {s} 6: return T 7: function LOCALSEARCHSUBSET(S) 8: X0 , Y0 S. 9: for i = 1 to |S| do 10: ai f(Xi 1 {si}) f(Xi 1), bi f(Yi 1 \ {si}) f(Yi 1) 11: a i max(ai, 0), b i max(bi, 0) 12: if a i = b i = 0 then a i/(a i + b i) = 0

13: with probability a i/(a i + b i) do: 14: Xi Xi 1 {si}, Yi Yi 1 15: else do: Xi Xi 1, Yi Yi 1 \ {si} 16: return X|S| (or equivalently Y|S|)

Analysis. In this section, we prove the correctness of our algorithms and analyze the number of oracle queries of our algorithms, which finishes the proof of Theorems 1.2.

Consider an arbitrary time t. Let St be the reported set of DYNAMICTHRESHOLDING at time t. Recall that Vt is the ground set at time t, and we drop the t for simplicity, so we use V and S to denote Vt and St. We first present Lemma 2.3 whose proof is given in the appendix. Then we proceed to prove Lemma 2.1 and Theorem 1.2

Lemma 2.3. Suppose that set S satisfies Property 1.b of Definition 1.1. It means that S has less than k elements and for any v V \ S, the marginal gain (v|S) < τ. Then, for any arbitrary subset C V , we have f(S) f(S C) |C| τ.

Proof of Lemma 2.1: Assume that at a fixed time t, OPT and S are the optimal value and an optimal solution for the submodular maximization of function f under cardinality constraint k. This means that |S | k and f(S ) = OPT . Recall that τ = OP T k(3+ 1

2α ), where OPT is our

guess for the optimal value. Also, by assumption we have OPT [ OP T

1+ϵ , OPT], or equivalently OPT [OPT , (1 + ϵ )OPT ].

To prove the lemma, we claim that max(E[f(S1)], E[f(S 1)], E[f(S2)]) (1 O(ε )) OP T

Suppose this claim is true. Using Jensen s inequality [23], we have E[max(f(S1), f(S 1), f(S2))] max(E[f(S1)], E[f(S 1)], E[f(S2)]) , which yields E[f(S)] (1 O(ε )) OP T

To prove the claim, we consider two cases. The first case is when f(S1 S ) τk

2α and the second case is if f(S1 S ) < τk

Suppose the first case is true. Then, the subset selection algorithm (either random sampling method or local search) returns S 1 for which E[f(S 1)] α max S S1 f(S). Since S1 S S1, we have

For the latter case, we show that E[f(S1)] + E[f(S2)] (1 O(ε )) OP T

3+1/2α, inferring

max (E[f(S1)], E[f(S2)]) (1 O(ε )) OP T

6+1/α. Indeed, since S1 and S2 are reported by an τ-thresholding algorithm, if |S1| = k or |S2| = k, then max(E[f(S1)], E[f(S2)]) is at least τk = OP T 3+1/2α by the first property of τ-thresholding algorithms.

Now suppose that |S1|, |S2| < k, which means that Property 1.b of Definition 1.1 holds for S1 and S2. Therefore, we have f(S1) f(S1 S ) τ|S | and f(S2) f(S2 (S \ S1)) τ|S \ S1| by Lemma 2.3. Besides, we have f(S1 S ) τk

2α < 0. Therefore,

f(S1) + f(S2) f(S1 S ) τ|S | + f(S2 (S \ S1)) τ|S \ S1| + f(S1 S ) τk

Since |S \ S1| |S | k we have

f(S1) + f(S2) f(S1 S ) + f(S2 (S \ S1)) + f(S1 S ) (2 + 1/(2α))τk .

Since S1 S2 = and f is submodular, we have f(S1 S ) + f(S2 (S \ S1)) f(S1 S2 S ) + f(S \ S1). Additionally, by the submodularity and non-negativity of f, we have f(S1 S ) f(S ) f(S \ S1), because f(S \ S1) + f(S1 S ) f(S ) + f( ). By adding the last two inequalities and using the non-negativity of f once again, we get f(S1 S ) + f(S2 (S \ S1)) + f(S1 S ) f(S1 S2 S ) + f(S ) f(S ) = OPT . By putting everything together we have,

f(S1) + f(S2) OPT (2 + 1/(2α))τk = OPT (4α + 1

2α )(OPT(2α)

By using the assumption that OPT (1 + ϵ )OPT , we have,

f(S1)+f(S2) OPT (1 ((4α + 1)(1 + ϵ )

6α + 1 )) OPT (2α ϵ (4α + 1)

6α + 1 ) = (1 O(ε )) OPT

3 + 1/(2α).

Proof of Theorem 1.2:

As previously discussed, we ve established in Lemma 2.1 and Corollary 2.2 that utilizing the local search method for the SUBSETSELECTION subroutine results in an approximation ratio of (8 + ε), whereas the random sampling method achieves an approximation ratio of (10 + ε). Thus, the only remaining aspect to address in proving this theorem is proving the query complexity of our proposed algorithm. In Lemma 2.4, we bound the number of queries made in each run of our algorithm per update, proving the bounds given in Theorem 1.2 by considering the extra O(ε 1 log k)-factor caused by our parallel runs.

Lemma 2.4. Let the random variable Qt denote the number of oracle calls that our algorithm in Theorem 1.2 makes at time t in each of the parallel runs. Depending on whether the expected or expected amortized number of oracle calls made by the thresholding algorithm DYNAMICTHRESHOLD per each update is O(g(n, k)), if we choose the local search method as our SUBSETSELECTION subroutine, we have E[Qt] O(min(k g(n, k), g(n, k)2)) + O(k) , or

t=1 Qt] O(T min(k g(n, k), g(n, k)2)) + O(k) ,

and if we choose the random sampling method as our SUBSETSELECTION subroutine, we have

E[Qt] O(min(k g(n, k), g(n, k)2)) ,

t=1 Qt] O(T min(k g(n, k), g(n, k)2))

Proof. Consider the case where the expected number of oracle calls made by the thresholding algorithm DYNAMICTHRESHOLD per each update is O(g(n, k)). Per each update, our algorithm makes an update in instance I1 causing O(g(n, k)) oracle queries. Next, we make either O(k) or 0 oracle queries for the SUBSETSELECTION subroutine, depending on the used method. We also make a series of updates in instance I2, each causing O(g(n, k)) oracle queries. The number of such updates is bounded by the number of changes in the output of instance I1, which is bounded by both k and O(g(n, k)) (according to the second property of Definition 1.1). These comprise all the oracle queries made by our algorithm at time t. Therefore, the given bounds for this case hold. A detailed proof for the remaining bounds is provided in the appendix.

3 Empirical results

In this section, we empirically study our (8+ε)-approximation dynamic algorithm. We implement our codes in C++ and run them on a Mac Book laptop with 8 GB RAM and M1 processor. We empirically study the performance of our algorithm for video summarization and the Max-Cut problem.

Video summarization. Here, we use the Determinantal Point Process (DPP) which is introduced by [42], and combine it with our algorithm to capture a video summarization. We run our experiments on You Tube and Open Video Project (OVP) datasets from [20].

For each video, we use the linear method of [33] to extract a subset of frames and find a positive semi-definite kernel L with size n n where n is the number of extracted frames. Then, we try to find a subset S of frames such that it maximizes det(LS) det(I+L) where LS is the sub-matrix of L restricted to indices corresponding to frames S. Since L is a positive semi-definite matrix, we have det(LS) 0. Interestingly, [39] showed that log(det(LS)) is a non-monotone function. We use these properties and set f(S) := log(det(LS) + 1) to make f a non-monotone non-negative submodular function. Then we run our (8 + ε)-approximate dynamic algorithm to find the best S to maximize f(S) such that |S| k for k [10].

Figure 1: Video summarization of Susan Boyle s performance on Britain s Got Talent show (video 106) from You Tube.

Figure 2: Video summarization for "Senses And Sensitivity, Introduct. to Lecture 1 presenter" (video 36) from OVP.

First, we insert all frames to observe the quality of our algorithm. Figure 1 and 2 are the selected frames by our algorithm for Video 106 from You Tube and Video 36 from OVP, respectively, when we limit the number of selected frames to 4. Then, we create a sequence Ξ of updates of frames of each video. Similar to [40], we define the sequence as a sliding window model. That is, given a window of size W for a parameter W N, a frame is inserted at a time t and will be alive for a window of size W and then we delete that frame.

To evaluate the performance of our algorithm, we benchmark (See Figure 3) the total number of query calls and the submodular value of set S of our algorithm and the streaming algorithm proposed for non-monotone submodular maximization so-called SAMPLE-STREAMING proposed in [28]. This algorithm works as follows: Upon arrival of an element u, with probability (1 q), for a parameter 0 < q < 1, we ignore u, otherwise (i.e., with probability q), we do the following. If the size of set S that we maintain is less than k, i.e, |S| < k and (u|S) > 0, we add u to S. However, if |S| = k, we select an element v S for which (v : S) is minimum possible, where (u : S) equals to (u|Su) where Su are elements that arrived before u in sequence Ξ. If (u|S) (1 + c) (v : S) for a constant c, we replace v by u; otherwise, we do nothing. Now we convert this streaming algorithm into a dynamic algorithm. To accomplish this, we restart SAMPLE-STREAMING after every deletion that deletes an element of solution set S that is reported by SAMPLE-STREAMING s outputs. That is, if a deletion does not touch any element in set S, we do nothing; otherwise we restart the streaming algorithm.

2 4 6 8 10 0

oracle calls

SAMPLE-STREAMING OUR DYNAMIC ALGORITHM

2 4 6 8 10 0

oracle calls

SAMPLE-STREAMING OUR DYNAMIC ALGORITHM

2 4 6 8 10 0

SAMPLE-STREAMING OUR DYNAMIC ALGORITHM

2 4 6 8 10 0 2 4 6 8 10

SAMPLE-STREAMING OUR DYNAMIC ALGORITHM

(a) (b) (c) (d)

Figure 3: We plot the total number of query calls and the average output of our dynamic algorithm and SAMPLE-STREAMING on video 106 from You Tube and video 36 from OVP. In this figure, from left to right, Sub-figures (a) and (b) are the total oracle calls for video 106 and 36, respectively. Similarly, Sub-figures (c) and (d) are average submodular value for video 106 and 36, respectively.

We run our algorithm for ε = k/2 and compare the total oracle calls and average output of our algorithm and SAMPLE-STREAMING in Figure 3. To prove the approximation guarantee of our dynamic algorithm, we assumed ε 1. However, in practice, it is possible to increase ε up to a certain level without affecting the output of the algorithm significantly. On the other hand, increasing ε reduces the total oracle calls and makes the algorithm faster. As you can see in Figure 3 plots (b) and (d), the submodular value of our algorithm is not worse than the SAMPLE-STREAMING algorithm whose approximation factor is 3 + 2

2 5.828 which is better than our approximation factor. Thus, our algorithm has an outcome better than our expectation, while its total oracle calls are better than SAMPLE-STREAMING algorithm (look at Figure 3 plots (a) and (c)).

We also empirically study the celebrated Max-Cut problem which is a non-monotone submodular maximization function (See [27]). These experiments are given in the appendix.

4 Conclusion

In this paper, we studied non-monotone submodular maximization subject to cardinality constraint k in the dynamic setting by providing a reduction from this problem to maximizing monotone submodular functions under the cardinality constraint k with a certain kind of algorithms(τ-thresholding algorithms). Moreover, we used our reduction to develop the first dynamic algorithms for this problem. In particular, both our algorithms maintain a solution set whose submodular value is a (8 + ε)- approximation of the optimal value and require O(ε 3k3 log3(n) log(k)) and O(ε 1k2 log3(k)) oracle queries per update, respectively.

5 Acknowledgements

This work is partially supported by DARPA Qu ICC NSF AF:Small #2218678, and NSF AF:Small #2114269.

[1] Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal streaming algorithms for submodular maximization with cardinality constraints. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 6:1 6:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[2] Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 47(4):2667 2690, 2022.

[3] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137 147, 1999.

[4] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: massive data summarization on the fly. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014.

[5] Eric Balkanski, Adam Breuer, and Yaron Singer. Non-monotone submodular maximization in exponentially fewer iterations. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS 18, page 2359 2370, Red Hook, NY, USA, 2018. Curran Associates Inc.

[6] Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, Mohammad Taghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic algorithms for matroid submodular maximization. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, ar Xiv:2306.00959.

[7] Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, Mohammadtaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic constrained submodular optimization with polylogarithmic update time. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 1660 1691. PMLR, 23 29 Jul 2023.

[8] Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Morteza Zadimoghaddam. Submodular secretary problem and extensions. ACM Trans. Algorithms, 9(4):32:1 32:23, 2013.

[9] Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Morteza Zadimoghaddam. Submodular secretary problem and extensions. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 39 52. Springer, 2010.

[10] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a nonsymmetric technique. Math. Oper. Res., 44(3):988 1005, 2019.

[11] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization. SIAM J. Comput., 44(5):1384 1402, 2015.

[12] Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 14, page 1433 1452, USA, 2014. Society for Industrial and Applied Mathematics.

[13] Larry Carter and Mark N. Wegman. Universal classes of hash functions (extended abstract). In Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 106 112, 1977.

[14] Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming, pages 318 330, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.

[15] Xi Chen and Binghui Peng. On the complexity of dynamic submodular maximization. In Stefano Leonardi and Anupam Gupta, editors, STOC 22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1685 1698. ACM, 2022.

[16] Yixin Chen and Alan Kuhnle. Practical and parallelizable algorithms for non-monotone submodular maximization with size constraint, 2022.

[17] Abhimanyu Das and David Kempe. Algorithms for subset selection in linear regression. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 45 54. ACM, 2008.

[18] Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011, pages 1057 1064. Omnipress, 2011.

[19] Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. J. Mach. Learn. Res., 19:3:1 3:34, 2018.

[20] Sandra Eliza Fontes de Avila, Ana Paula Brandão Lopes, Antonio da Luz Jr., and Arnaldo de Albuquerque Araújo. VSUMM: A mechanism designed to produce static video summaries and a novel evaluation method. Pattern Recognit. Lett., 32(1):56 68, 2011.

[21] Delbert Dueck and Brendan J. Frey. Non-metric affinity propagation for unsupervised image categorization. In IEEE 11th International Conference on Computer Vision, ICCV 2007, Rio de Janeiro, Brazil, October 14-20, 2007, pages 1 8. IEEE Computer Society, 2007.

[22] Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. Fully dynamic submodular maximization over matroids. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 8821 8835. PMLR, 23 29 Jul 2023.

[23] Rick Durrett. Probability: Theory and Examples, 4th Edition. Cambridge University Press, 2010.

[24] Khalid El-Arini and Carlos Guestrin. Beyond keyword search: discovering relevant scientific literature. In Chid Apté, Joydeep Ghosh, and Padhraic Smyth, editors, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011, pages 439 447. ACM, 2011.

[25] Ethan R. Elenberg, Rajiv Khanna, Alexandros G. Dimakis, and Sahand N. Negahban. Restricted strong convexity implies weak submodularity. Co RR, abs/1612.00804, 2016.

[26] Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1833 1842. PMLR, 2019.

[27] Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM J. Comput., 40(4):1133 1153, 2011.

[28] Moran Feldman, Amin Karbasi, and Ehsan Kazemi. Do less, get more: Streaming submodular maximization with subsampling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, Neur IPS 2018, December 3-8, 2018, Montréal, Canada, pages 730 740, 2018.

[29] Moran Feldman, Joseph Naor, and Roy Schwartz. Nonmonotone submodular maximization via a structural continuous greedy algorithm - (extended abstract). In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, volume 6755 of Lecture Notes in Computer Science, pages 342 353. Springer, 2011.

[30] Satoru Fujishige. Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions. Math. Program., 29(2):142 155, 1984.

[31] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 11, page 1098 1116, USA, 2011. Society for Industrial and Applied Mathematics.

[32] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1098 1116. SIAM, 2011.

[33] Boqing Gong, Wei-Lun Chao, Kristen Grauman, and Fei Sha. Diverse sequential subset selection for supervised video summarization. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 2069 2077, 2014.

[34] Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In Amin Saberi, editor, Internet and Network Economics - 6th International Workshop, WINE 2010, Stanford, CA, USA, December 13-17, 2010. Proceedings, volume 6484 of Lecture Notes in Computer Science, pages 246 257. Springer, 2010.

[35] Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. Optimal marketing strategies over social networks. In Proceedings of the 17th international conference on World Wide Web, pages 189 198, 2008.

[36] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 53(3):307 323, 2006.

[37] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 2549 2558. PMLR, 2018.

[38] Rajiv Khanna, Ethan R. Elenberg, Alexandros G. Dimakis, Sahand N. Negahban, and Joydeep Ghosh. Scalable greedy feature selection via weak submodularity. In Aarti Singh and Xiaojin (Jerry) Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pages 1560 1568. PMLR, 2017.

[39] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. Found. Trends Mach. Learn., 5(2-3):123 286, 2012.

[40] Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Morteza Zadimoghaddam. Fully dynamic algorithm for constrained submodular optimization. In Hugo Larochelle, Marc Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, Neur IPS 2020, December 6-12, 2020, virtual, 2020.

[41] Paul Liu and Jan Vondrák. Submodular optimization in the mapreduce model. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8-9, 2019 - San Diego, CA, USA, volume 69 of OASICS, pages 18:1 18:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.

[42] Odile Macchi. The coincidence approach to stochastic point processes. Advances in Applied Probability, 7(1):83 122, 1975.

[43] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1358 1367, New York, New York, USA, 20 22 Jun 2016. PMLR.

[44] Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Sheila A. Mc Ilraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 1379 1386. AAAI Press, 2018.

[45] Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Deletion-robust submodular maximization: Data summarization with "the right to be forgotten". In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2449 2458. PMLR, 2017.

[46] Morteza Monemizadeh. Dynamic submodular maximization. In Hugo Larochelle, Marc Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, Neur IPS 2020, December 6-12, 2020, virtual, 2020.

[47] Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovic, Amir Zandieh, Aidasadat Mousavifar, and Ola Svensson. Beyond 1/2-approximation for submodular maximization on massive data streams. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3826 3835. PMLR, 2018.

[48] Binghui Peng. Dynamic influence maximization. In Marc Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, Neur IPS 2021, December 6-14, 2021, virtual, pages 10718 10731, 2021.

[49] Sharon Qian and Yaron Singer. Fast Parallel Algorithms for Statistical Subset Selection Problems. Curran Associates Inc., Red Hook, NY, USA, 2019.

[50] Ian Simon, Noah Snavely, and Steven M. Seitz. Scene summarization for online image collections. In IEEE 11th International Conference on Computer Vision, ICCV 2007, Rio de Janeiro, Brazil, October 14-20, 2007, pages 1 8. IEEE Computer Society, 2007.

[51] Ruben Sipos, Adith Swaminathan, Pannaga Shivaswamy, and Thorsten Joachims. Temporal corpus summarization using submodular word coverage. In Xue-wen Chen, Guy Lebanon, Haixun Wang, and Mohammed J. Zaki, editors, 21st ACM International Conference on Information and Knowledge Management, CIKM 12, Maui, HI, USA, October 29 - November 02, 2012, pages 754 763. ACM, 2012.

[52] Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.