Efficient streaming algorithms for maximizing monotone DR-submodular function on the integer lattice

Citation: Nguyen, B.-N.T.; Pham, P.N.H.; Le, V.-V.; Snášel, V. Efficient Streaming Algorithms for Maximizing Monotone DR-Submodular Function on the Integer Lattice. Mathematics 2022,10, 3772. https://doi.org/10.3390/ math10203772 Academic Editors: Gaogao Dong and Jianguo Liu Received: 1 September 2022 Accepted: 9 October 2022 Published: 13 October 2022 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). mathematics Article Efficient Streaming Algorithms for Maximizing Monotone DR-Submodular Function on the Integer Lattice Bich-Ngan T. Nguyen 1,2 , Phuong N. H. Pham 1,2,* , Van-Vang Le 3and Václav Snášel 2 1Faculty of Information Technology, Ho Chi Minh City University of Food Industry, 140 Le Trong Tan Street, Ho Chi Minh City 700000, Vietnam 2Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VŠB-Technical University of Ostrava, 17.listopadu 15/2172, 708 33 Ostrava, Czech Republic 3Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City 700000, Vietnam *Correspondence: [email protected] Abstract: In recent years, the issue of maximizing submodular functions has attracted much interest from research communities. However, most submodular functions are specified in a set function. Meanwhile, recent advancements have been studied for maximizing a diminishing return submodular (DR-submodular) function on the integer lattice. Because plenty of publications show that the DR-submodular function has wide applications in optimization problems such as sensor placement impose problems, optimal budget allocation, social network, and especially machine learning. In this research, we propose two main streaming algorithms for the problem of maximizing a monotone DR-submodular function under cardinality constraints. Our two algorithms, which are called StrDRS1 and StrDRS2 , have ( 1 / 2 −e) , ( 1 − 1 /e−e) of approximation ratios and O(n elog(log B e)log k) , O(n elog B) , respectively. We conducted several experiments to investigate the performance of our algorithms based on the budget allocation problem over the bipartite influence model, an instance of the monotone submodular function maximization problem over the integer lattice. The experimental results indicate that our proposed algorithms not only provide solutions with a high value of the objective function, but also outperform the state-of-the-art algorithms in terms of both the number of queries and the running time. Keywords: DR-submodular function; integer lattice; adaptive complexity; approximation algorithm MSC: 03G10; 06C05; 06D99; 30E10; 65K10 1. Introduction Submodular function maximization problems have recently received great interest in the research community. A satisfactory explanation for this attraction is the prevalence of optimization problems related to submodular functions in many real-world applications [ 1 ]. Prominent examples include sensor placement problems [ 2 , 3 ] and facility location [ 4 ] in operational improvement, the influence maximization problem in viral marketing [ 5 , 6 ], document summarization [ 7 ], experiment design [ 8 ], dictionary learning [ 9 ] in machine learning, etc. These problems can be presented with the concept of submodularity, and effective algorithms have been developed taking advantage of the submodular function [ 10 ]. Given a ground set E, a function f:2E→R≥0is called submodular if for all A,B⊆E, f(A) + f(B)≥f(A∪B) + f(A∩B)(1) The submodularity of a submodular function f is equivalent to the property diminishing return, i.e., for any A⊆B⊆Eand ∀e∈E\B, it holds. f(A∪e)−f(A)≥f(B∪e)−f(B)(2) Mathematics 2022,10, 3772. https://doi.org/10.3390/math10203772 https://www.mdpi.com/journal/mathematics Mathematics 2022,10, 3772 2 of 19 and the set function fis called monotone if f(A)≤f(B)for any A⊆B⊆E(3) The submodular function maximization problem aims to select a subset A of the ground set Eto maximize f(A). Most existing studies of the submodular function maximization problem consider submodular functions identified over a set function. It means that the problem has the input as a subset of the ground set and returns an actual value. However, there are many real-world situations in which it is crucial to know whether an element e∈E is selected and how many copies of that element should be chosen. In other words, the problem considers submodular functions over a multiset, under the name submodular function on the integer lattice [ 11 ]. The submodularity defined on the integer lattice differs from set functions because it does not equate to the diminishing return property. Some notable examples include the optimal budget allocation problem [ 12 ], document summarization and sensor placement [ 13 ], the submodular welfare problem [ 14 ], and maximization of influence spread with partial incentives [ 15 ]. The definitions of a submodular function and diminishing return submodular function on the integer lattice are as follows: A function f:ZE +→Ris a submodular function on the integer lattice if for all x,y∈ZE + f(x) + f(y)≥f(x∨y) + f(x∧y)(4) where x∧yand x∨ydenote the coordinate-wise min and max operations, respectively. A function f:ZE +→R is called diminishing return submodular (DR-submodular), if for all x,y∈ZE +with x≤y f(x+χe)−f(x)≥f(y+χe)−f(y)(5) where e∈E and χe denote the unit vector with coordinate e being 1 and the other elements are 0. The submodularity defined on the integer lattice differs from the set functions because it does not equate to the diminishing return property. In other words, lattice submodularity is weaker than DR-submodularity, i.e., a lattice submodular function may not be a DR-submodular function, but any DR-submodular function is a lattice submodular one [ 11 ]. Due to this cause, developing approximation algorithms is challenging; even for a single cardinality constraint, we need a more complicated method, such as partial enumeration [ 12 , 13 ]. Nevertheless, the diminishing return property of the DR-submodular function maximization problem often plays a fundamental role in some practical problems, such as optimizing budget allocation among channels and influencers [ 12 ], optimal budget allocation [13], and online submodular welfare maximization [14]. There have been many approaches to solving the problem of maximizing the submodular function under different constraints and contexts in the last decade. Two notable approaches to this problem are greedy algorithms [ 16 – 19 ] and streaming algorithms [20–22] . Plenty of studies show that the greedy method is often used for this optimization problem because it outputs a better result than other methods due to its “greedy” operation [ 16 , 23 , 24 ]. Understandably, the greedy method always scans data many times to find the best. However, this causes its algorithms to have a long runtime; it cannot even be applied to big data. Contrary to the greedy method, the streaming method scans the data once. As each element in the dataset arrives in order, the streaming algorithm must decide whether that element is selected before the next element arrives. Thus, the result of this method may not be as good as the result of greedy, because the elements it selects are not the best, but meet the selection condition. However, the outstanding advantage of the streaming method is that it runs much faster than the greedy method [ 25 ]. There are many studies that have used the streaming method to resolve the issue of submodular function maximization. Those studies have shown the advantages of the streaming method compared to the greedy Mathematics 2022,10, 3772 3 of 19 method. Some prominent studies include using the streaming algorithm for maximizing k -submodular functions under budget constraints [ 26 ], optimizing a submodular function under noise by streaming algorithms [ 27 ], maximizing a monotone submodular function by multi-pass streaming algorithms [ 20 ], and using fast streaming for the problem of submodular maximization [22]. Attracted by the usefulness of the maximizing DR-submodular function on the integer lattice issue in many practical problems, numerous studies on this problem have recently been published. These publications consider the problem under many different constraints and use greedy or streaming methods as the standard approach. Some prominent examples include the use of a fast double greedy algorithm to maximize the non-monotone DR submodular function [ 24 ], using a threshold greedy algorithm to maximize the monotone DR submodular constraint knapsack over an integer lattice [ 28 ], combining the threshold greedy algorithm with a partial element enumeration technique to maximize the monotone DR submodular knapsack constraint over an integer lattice [ 11 ], using a streaming method to maximize DR-submodular functions with d -knapsack constraints [ 29 ], using a one-pass streaming algorithm for DR-submodular maximization with a knapsack constraint over the integer lattice [ 30 ], and using streaming algorithms for maximizing a monotone DRsubmodular function with a cardinality constraint on the integer lattice [31]. Our contribution . In this paper, we focus on the maximization of monotone DR-submodular function under cardinality constraint on the integer lattice (the MDRSCa problem in Definition 2). In surveying the literature, there are two novel methods for this problem. First, Soma et al. [ 11 ] proposed the Cardinality constraint/DR-submodular algorithm (called CaDRS ), which interpolates between the classical greedy algorithm and a truly continuous algorithm. This algorithm achieves an approximation ratio of (1 − 1 /e−e ) in O(n elog Blog k e) complexity. Second, Zhang et al. [ 31 ] first devised a streaming algorithm based on Sieve streaming [ 32 ]. Zhang’s method achieves an approximation ratio of (1 / 2 −e ) in O(k e) memory and O(k elog2k) query complexity. Inspired by Zhang’s method [ 31 ], our study based on the streaming method devises two improved streaming algorithms for the problem and obtains some positive results compared to state-of-the-art algorithms. Specifically, our main contributions are as follows. • To resolve the MDRSCa problem, we first devise an algorithm (called StrOpt ) to handle each element by scanning the data with the assumption of a known optimal value ( OPT ). We prove that StrOpt guarantees the theoretical result with an approximation ratio of ( 1 / 2 ) . Next, we devise a ( 1 / 4 ) -approximation streaming algorithm (called Stepping-Stone algorithm), which has the procedure role to calculate the threshold for the main algorithm. Later, based on StrOpt and Stepping-Stone algorithms, we provide two main streaming algorithms to solve this problem. They are named StrDRS1 and StrDRS2 . Because OPT cannot be determined in actual situations, we estimate OPT based on a conventional method by observing OPT ∈[m ,2 km] where m=maxe∈E{f(χe)} . Based on estimated OPT , StrDRS1 , a one-pass streaming algorithm, has an approximation ratio of (1 / 2 −e ) and takes O(n elog(log B e)log k) queries. For StrDRS2 , we first find a temporary result that satisfies the cardinality constraint by the Stepping-Stone algorithm. Subsequently, we increase the approximation solution ratio in StrDRS2 by finding elements that hold the threshold restriction of the above temporary result. The StrDRS2 is a multi-pass streaming algorithm that scans O(1 e) passes, takes O(n elog B) queries, and returns an approximation ratio of ( 1 − 1 /e−e) . • We further investigate the performance of our algorithms by performing some experiments on some datasets of practical applications. We run four algorithms, StrDRS1 , StrDRS2 , CaDRS [ 11 ], and SieveStr + + [ 31 ], to compare their performance. The results indicate that our algorithms provide solutions with a theoretically guaranteed value of the objective function and outperform the state-of-the-art algorithm in both the number of queries and the runtime. Mathematics 2022,10, 3772 4 of 19 Table 1shows how our algorithms compare theoretical properties with current stateof-the-art algorithms for the problem of maximizing monotone DR submodular functions with a cardinality constraint in the integer lattice. Table 1. State-of-the-art algorithms for the problem of monotone DR-submodular function maximization with a cardinality constraint on the integer lattice in terms of time complexity. Reference Pass Ratio Query Complexity CaDRS O(1 elog 1 e)1−1/e−eO(n elog Blog k e) SieveStr + + 1 1/2 −eO(k elog2k) StrDRS1 1 1/2 −eO(n elog(log B e)log k) StrDRS2 O(1 e)1−1/e−eO(n elog B) Organization. The structure of our paper is as follows: Section 1introduces the development situation of the submodular function maximization on a-set and multi-set. Primarily, we focus on maximizing the monotone DR-submodular function on the integer lattice under cardinality constraint and present the main contributions of our study. Section 2 reviews the related work. The definition of the problem and some notation are introduced in Section 3. Section 4contains our proposed algorithms and theoretical analysis. Section 5 shows the experimental results and evaluation. Finally, Section 6concludes the paper and future work. 2. Related Work A considerable amount of literature has been published on the maximization of monotone submodular functions under many different constraints over many decades. Nemhauser et al. [ 33 ] are pioneers in studying the approximations for maximizing submodular set functions in combinatorial optimization and machine learning. They proved that the standard greedy algorithm gives a (1 / 2)-approximation under a matroid constraint and a (1 − 1 /e )-approximation under a cardinality constraint. Their method served as a model for further development. Later, Sviridenko [ 34 ] developed an improved greedy algorithm for maximizing a submodular set function subject to a knapsack constraint. This algorithm achieves a (1 − 1 /e )-approximation with O(n5) time complexity for a knapsack constraint. Subsequently, Calinescu et al. [ 35 ] first devise a (1 − 1 /e )-approximation algorithm for maximizing a monotone submodular function subject to a matroid constraint. This method combines a continuous greedy algorithm and pipage rounding. The pipage rounding rounds the approximate fractional solution of the continuous greedy approach to obtain an integral feasible solution. Recently, Badanidiyuru et al. [ 36 ] design a (1 − 1 /e−e )- approximation algorithm with any fixed constraint e> 0 for maximizing submodular functions. This algorithm takes O(n elog n e)time complexity for the cardinality constraint. Several studies have recently begun investigating the maximization of DR-submodular functions on the integer lattice under various constraints. Soma et al. (2014) [ 13 ] studied the monotone DR-submodular function maximization over integer lattices under a knapsack constraint. They proposed a simple greedy algorithm, which has an approximation ratio of (1 − 1 /e ) and a pseudo-polynomial time complexity. Next, Soma et al. (2018) [ 11 ] continued to develop polynomial-time approximation algorithms for the problem of DR-submodular function maximization under a cardinality constraint, a knapsack constraint, and a polymatroid constraint on the integer lattice, respectively. For the cardinality constraint, they devised an algorithm based on the decreasing threshold greedy framework. For the polymatroid constraint, they developed an algorithm based on an extension of continuous greedy algorithms. For the knapsack constraint, they used the decreasing threshold greedy framework as the algorithm of the cardinality constraint. However this algorithm takes its initial solution as an input, whereas the algorithm for cardinality constraints always uses the zero vector as the initial solution. All three algorithms have polynomial time and Mathematics 2022,10, 3772 5 of 19 achieve a (1 − 1 /e−e )-approximation ratio. Besides, Some et al. (2017) [ 37 ] also studied the problem of non-monotone DR-submodular function maximization. They proposed a double greedy algorithm, which has 1 2+e -approximation and O(n elog2B) . Subsequently, Gu et al. (2020) [ 24 ] study the problem of maximizing the non-monotone DR-submodular function on the bounded integer lattice. They propose a fast double greedy algorithm that improves runtime. Their result achieves a 1 / 2-approximation algorithm with a O(nlog B) time complexity. Liu et al. (2021) [ 29 ] develop two streaming algorithms for maximizing DR-submodular functions under the d -knapsack constraints. The first is a one-pass streaming algorithm that achieves a (1−θ 1+d) -approximation with O(log(dβ−1) βe ) memory complexity and O(log(dβ−1) elog B) update time per element, where θ=min(α+e ,0.5 +e) and α , β are the upper and lower bounds for the cost of each item in the stream. The second is an improved streaming algorithm to reduce the memory complexity to O(d βe ) with an unchanged approximation ratio and query complexity. Zhang et al. (2021) [ 31 ] based on the Sieve streaming method to develop a streaming algorithm for the problem of monotone DR-submodular function under cardinality constraint on the integer lattice. This algorithm achieves an approximation ratio of ( 1 / 2 −e) and takes O(k elog2k) complexity. This is the problem that we study in this paper. Most recently, Tan et al. (2022) [ 30 ] design an one-pass streaming algorithm for the problem of DR-submodular maximization with a knapsack constraint over the integer lattice, called DynamicMRT, which achieves a ( 1 / 3 −e) -approximation ratio, a memory complexity O(Klog K/e) , and query complexity O(log2K/e) per element for the knapsack constraint K . Meanwhile, Gong et al. (2022) [ 28 ] consider the problem of non-negative monotone DR-submodular function maximization over a bounded integer lattice. They present a deterministic algorithm and theoretically reduce its runtime to a new record, O((1 e O(1/e5) . nlog 1 cmin log B)) , (where cmin =mine∈Ec(e) and c(.)is a cost function defined in E) with the approximate ratio of (1 −1/e−O(e)). All the studies mentioned above consider the problem of maximizing the submodular function on a set function or maximizing the DR-submodular function on the integer lattice under different constraints. Only the studies of Soma et al. in [11] and Zhang et al. in [31] consider the problem of MDRSCa, as mentioned in the contribution section. Motivated by these studies, we proposed two improved streaming algorithms for the MDRSCa problem. Our algorithms achieve better than state-of-the-art methods through theoretical analysis and experimental results. 3. Preliminaries This section introduces the definitions of the monotone DR-submodular, MDRSCa problem and its associated notations. Table 2summarizes the usually used notations in this paper. Mathematics 2022,10, 3772 6 of 19 Table 2. Table of the usually used notations in this paper. Notation Description Ea ground set, E={e1, . . . , en} nthe number of elements in the ground set E. 2Ethe subset family of E. A,Bthe arbitrary subsets of E x,ythe arbitrary vectors of ZE + χethe unit vector with coordinate e,e∈E {x}the multiset contains elements in vector x, where each element e∈Ecan appear many times. x(e),y(e)the coordinate value of entry ein vector x,y, where e∈E kxk∞the infinity norm of vector x,kxk∞:=maxe∈Ex(e) kxk1the taxicab norm of vector x,kxk1:=∑e∈Ex(e). 0the vector zero whose value 0(e) = 0, ∀e∈E Bthe upper bound vector of x,0≤x≤B B B :=kBk∞ kthe upper bound of total elements in vector xon the integer lattice ZE +,x(E)≤k kethe number of copies of eto be considered for addition to x k0the number of copies of eadd to x [k]the set of {1, . . . , k} van optimal value of the object function, (1−e)OPT ≤v≤OPT with (e∈(0, 1/2)) x∨ythe coordinate-wise maximum of xand y (x∨y)(e)x∨y:=max{x(e),y(e)} x∧ythe coordinate-wise minimum of xand y (x∧y)(e)x∨y:=min{x(e),y(e)} x+ysum of 2 vectors xand y, with the multiset {x+y}whose eappears (x(e) + y(e)) times. x−y x −y=x+ (−y) f(x)the object function value of x f(x|y)f(x|y) = f(x+y)−f(y) 3.1. Notation For a positive integer k∈N , [k] denotes the set { 1, . . . , k} . Given a ground set E={e1 , . . . , en} , we denote the i -th entry of a vector x∈ZE + by x(i) , and for each e∈E , we define the e-th unit vector with χe(t) = 1 if t=eand χe(t) = 0 if t6=e. For x∈ZE + , {x} denotes the multiset where the element e appears x(e) times and with a subset A⊆E , x(A) = ∑e∈Ax(e) and supp+(x) = {e∈E|x(e)> 0 } . According to the definition of the vector norm, we have kxk∞:=maxe∈Ex(e)and kxk1:=∑e∈Ex(e). For two vectors x , y∈ZE + , x≤y signifies ∀e∈E then x(e)≤y(e) . Furthermore, given x , y∈ZE + , x∨y and x∧y denote the coordinate-wise maximum and minimum, respectively. This means that (x∨y)(e):=max{x(e) , y(e)} and (x∧y)(e):=min{x(e) , y(e)} . In addition, x+y denotes the multiset {x+y} where the element e appears (x(e) + y(e)) times. Thus, we can infer x−y=x+ (−y). 3.2. Definition For function f:ZE +→R+, we define f(x|y) = f(x+y)−f(y). Definition 1 ( Monotone DR-submodular function ) . A function f:ZE +→R+ is monotone if f(x)≤f(y ) for all x , y∈ZE + with x≤y and f is said to be diminishing return submodular (DR-submodular), if f(x+χe)−f(x)≥f(y+χe)−f(y)(6) Mathematics 2022,10, 3772 7 of 19 Definition 2 ( Maximization of monotone DR-submodular function under cardinality constraint on the integer lattice—MDRSCa problem ) . Let B∈ZE + , B=kBk∞ and an integer k >0, we consider the DR-submodular function under cardinality constraint as follows maximize:f (x)subject to: 0≤x≤B,x(E)≤k(7) 4. Proposed Algorithm This section presents descriptions and theoretical analysis of the algorithms we have proposed for the MDRSCa problem, including a streaming algorithm with the assumption that the optimal value is known ( StrOpt ), the Stepping-Stone algorithm and two main streaming algorithms (StrDRS1,StrDRS2). 4.1. Streaming Algorithm with Approximation Ratio of (1/2 −e) First, we propose StrOpt , a single-pass streaming algorithm for the MDRSCa problem under the assumption that the optimal value of the objective function is known. Afterwards, we use the traditional method to estimate the optimal value and devise the main one-pass streaming algorithm called StrDRS1. 4.1.1. Algorithm with Knowing Optimal Value—StrOpt Algorithm description. The detail of StrOpt is fully presented in Algorithm 1. Algorithm 1: StrOpt(f,B,k,e,v) Input: f:ZE +→R+,B,k,e, a guess of optimal value v Output: A vector x 1: x←0 2: foreach e∈Edo 3: I← {i1,i2, . . . , i|I|}:i1<i2. . . <i|I|} ← {dB(e)(1−e)ie:i∈Z,1 ≤ B(e)(1−e)i≤B(e)} 4: Find ke←argmin{ij−1 : ij∈I,f(ijχe|x)/ij<v 2k}by a binary search 5: k0←min{ke,k− kxk1} 6: if k06=0then 7: x←x+k0·χe 8: else 9: break 10: return x We assume that the optimal value OPT of the objective function of MDRSCa is already known. StrOpt is created to find vector x using this OPT . Given a known optimal value v that satisfies ( 1 −e)OPT ≤v≤OPT for any e∈( 0, 1 2) . When each element e arrives, we find a set I , which is the set of positive integers predicted to be the number of copies of e . Then, we use the binary search with threshold v 2k to find the minimum ke that holds f(ke|x)/ke<v 2k . We denote by k0 the number of copies of e that adds the result vector x . The value k0 is the minimum of two values ke and the rest of elements x ’ in the cardinality k . If k0is equal to 0, then eis not selected in x. Otherwise, eis selected in xwith k0copies. Theoretical analysis. Lemma 1, Theorem 1, and their proofs demonstrate the theoretical solution guarantee of StrOpt . On the basis of that, we devise the first main streaming algorithm for the MDRSCa problem. Lemma 1. We have f (keχe|x)≥(1−e)kev 2k. Mathematics 2022,10, 3772 8 of 19 Proof. Assume that ke=ij=dxe where x=B(e)( 1 −e)i with some i∈I . We have ij≥ij−1+1 and ke−ij−1=ij−(ij−1+1) = dxe − (d(1−e)xe+1) ≤ dxe − (dxe+d(−ex)e) = −d(−ex)e =bexc ≤ ex≤eke Therefore, ij−1≥( 1 −e)ke . From the combination of the selection ke and the monotonicity of f, we have the following. f(keχe|x)≥f(ij−1χe|x)≥ij−1v 2k≥(1−e)kev 2k(8) The proof is completed. Theorem 1. For any e∈( 0,1 / 2 ) and ( 1 −e)OPT ≤v≤OPT , the Algorithm 1takes O(nlog(1 elog B)) queries and returns a solution xsatisfying f (x)≥(1−e)v/2. Proof. The Algorithm 1scans only one time over E and each incoming element e , it takes log |I|=O(log(1 elog B)) queries to find ke . The total number of required queries of the algorithm is O(nlog(1 elog B)). Denote xi and kiχei as the solution at the beginning of iteration i and the additional vector in the current solution at iteration i , respectively. We consider two following cases: Case 1. If kxk1=k, we have k1+k2+. . . +kn=kthus: f(x) = n ∑ i=1 f(kiχei|xi)≥ n ∑ i=1 (1−e)ki v 2k=(1−e)v 2(9) Case 2. If kxk1<k , after ending the main loop, we have f(e|x)≤v 2k for all e∈ {B−x} . Therefore: f(o)−f(x) = f(o∨x)−f(x) =∑ e∈{o∨x−x} f(χe|x) =∑ e∈{o−o∧x} f(χe|x) <∑ e∈{o−o∧x} v 2k≤v 2 where the second equality follows from the lattice identity x∨y−y=x−x∧y for x,y∈ZE +. We have f(x)≥OPT −v/2 ≥v/2. The proof is completed. Mathematics 2022,10, 3772 9 of 19 4.1.2. (1/2 −e)-Approximation Streaming Algorithm—StrDRS1 Algorithm Algorithm description. The detail of this algorithm is fully presented in Algorithm 2. Algorithm 2: Streaming-I algorithm (StrDRS1) Input: f:ZE +→R+,B,k,e Output: A(1/2 −e)-approximation solution x 1: O={(1+e)i|i∈Z+} 2: xv=0,∀v∈O,m←0 3: foreach e∈Edo 4: m←max{f(χe),m} 5: O={(1+e)i|i∈Z+,m≤(1+e)i≤2km} 6: I← {i1,i2, . . . , i|I|}:i1<i2. . . <i|I|} ← {dB(e)(1−e)ie:i∈Z,1 ≤ B(e)(1−e)i≤B(e)} 7: for v∈Odo 8: Find ke←argmin{i∈I:f(iχe|xv)<i·v 2k}by a binary search 9: k0←min{ke,k− kxvk1} 10: if k06=0then 11: xv←xv+k0·χe 12: else 13: break 14: return argmaxxv,v∈Of(xv) Based on the analysis of StrOpt , and the working frame of the Sieve streaming algorithm [ 38 ], we design the StrDRS1 algorithm for the MDRSCa problem with the following main idea. We find a set of solutions xv of OPT , where v∈O and O is the set of values that changes according to the maximum value of the unit standard vector on the arriving elements. Besides, we find a set I , which contains positive integers predicted to be the number of copies of each element e if e is selected in xv . For each solution xv , v∈O , the algorithm finds ke , is the smallest value in I so that the current element e satisfies the condition in line 8 by binary search. Then, we choose k0 , which is the minimum value between ke and k− kxvk1 . If k0 is not equal to 0, this means that e is selected in xv with k0 copies. Otherwise, e is not selected in xv . In the end, the result x is xv , which makes f(x)maximal. Theoretical analysis. We analyze the complexity of StrDRS1, stated in Theorem 2. Theorem 2. StrDRS1 is a single-pass streaming algorithm, has an approximation ratio of (1 2−e) and takes O(n elog(log B e)log k)queries. Proof. By the definition of O, there exists an integer isuch that (1−e)OPT ≤OPT 1+e≤v= (1+e)i≤OPT By applying the proof of Theorem 1, and the working frame of the Sieve streaming algorithm in [38], we obtain: f(xv)≥(1−e) 2v≥(1−e)2 2OPT ≥(1 2−e)OPT (10) The proof is completed. Mathematics 2022,10, 3772 16 of 19 number of queries. Table 4. Statistics of the number of queries. kStrDRS1 StrDRS2 CaDRS SieveStr + + FilmTrust rating 60 7601 40,895 240,202 183,453 70 8126 40,917 247,335 198,063 80 8582 40,939 252,978 202,716 90 8933 40,957 261,258 217,947 100 9613 40,979 264,730 225,569 NIPS full papers 120 10,934 40,807 206,599 13,595 140 11,040 40,847 209,606 15,106 160 11,108 40,887 215,624 17,690 180 13,313 40,927 218,639 19,362 200 14,446 40,963 221,672 22,958 Influence. Through the analysis of experimental results, the difference in the influence value of the algorithms is as follows. For the comparison of SieveStr + + and StrDRS1 , the influence of StrDRS1 is 1.1 to 1.2 times smaller than SieveStr + + . For the comparison of CaDRS and StrDRS2 , the influence of StrDRS2 is 1.0 to 1.3 times smaller than CaDRS for FilmTrust dataset. However, for NIPS dataset, the influence of StrDRS2 is 1.4 to 1.7 times greater than CaDRS in this parameters set. Generally, because CaDRS uses a greedy technique, the influence of this algorithm is always at its best. As k increases, this value of CaDRS can reach the best values. On the contrary, the remaining three algorithms use streaming techniques, so it is difficult to achieve the same influence as CaDRS ’s. However, the difference in the influence of streaming and greedy algorithms is not too large. Especially, this gap will decrease as k increases. Thus, the time benefit of our algorithms is a significant strength against this disparity in influence. For the convenience of the readers, we summarize the experimental results in Table 5. Table 5. Statistical comparison of experimental results. StrDRS1 vs. SieveStr + + Oracle queries StrDRS1 is 1.2 to 24.4 times smaller than SieveStr + + Time StrDRS1 is 1.1 to 102.5 times faster than SieveStr + + Influence StrDRS1 is 1.1 to 1.2 times smaller than SieveStr + + StrDRS2 vs. CaDRS Oracle queries StrDRS2 is 5.1 to 6.5 times smaller than CaDRS Time StrDRS2 is 2.0 to 4.8 times faster than CaDRS Influence For FilmTrust, StrDRS2 is 1.0 to 1.3 times smaller than CaDRS but StrDRS2 is 1.4 to 1.7 times greater than CaDRS for NIPS. 6. Conclusions and Future Work This paper studies the maximization of monotone DR-submodular functions with a cardinality constraint on the integer lattice. We propose two streaming algorithms that have determined approximation ratios and significantly reduce query and time complexity compared to state-of-the-art algorithms. We conducted some experiments to evaluate the efficiency of our algorithms and novel algorithms for this problem. The results indicate that our algorithms are highly scalable and outperform the compared algorithms in terms of both runtime and number of queries, and the influence is slightly smaller. For our future work, one direction is to study the monotone DR-submodular function maximization problem under a polymatroid constraint and knapsack constraint. In another Mathematics 2022,10, 3772 17 of 19 direction, we consider the maximization of the non-monotone DR-submodular function under a cardinality constraint. Author Contributions: Conceptualization, B.-N.T.N. and V.S.; formal analysis, B.-N.T.N.; investigation, B.-N.T.N. and P.N.H.P.; methodology, B.-N.T.N., P.N.H.P. and V.-V.L.; project administration, B.-N.T.N.; resources, B.-N.T.N.; software, B.-N.T.N. and P.N.H.P.; supervision, V.S.; validation, V.S.; writing—original draft, B.-N.T.N.; Writing—review and editing, B.-N.T.N., P.N.H.P., V.-V.L. and V.S. All authors have read and agreed to the published version of the manuscript. Funding: This research was supported by Ho Chi Minh City University of Food Industry (HUFI), Ton Duc Thang University (TDTU), and VŠB-Technical University of Ostrava (VŠB-TUO). Institutional Review Board Statement: Not applicable. Informed Consent Statement: Not applicable. Data Availability Statement: All real-world network datasets used in the experiment can be downloaded at http://konect.cc/ (accessed on 1 September 2022). Acknowledgments: The authors would like to give thanks for the support of Ho Chi Minh City University of Food Industry (HUFI), Ton Duc Thang University (TDTU), and VŠB-Technical University of Ostrava (VŠB-TUO). Conflicts of Interest: The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results. References 1. Tohidi, E.; Amiri, R.; Coutino, M.; Gesbert, D.; Leus, G.; Karbasi, A. Submodularity in action: From machine learning to signal processing applications. IEEE Signal Process. Mag. 2020,37, 120–133. [CrossRef] 2. Krause, A.; Guestrin, C.; Gupta, A.; Kleinberg, J. Near-optimal sensor placements: Maximizing information while minimizing communication cost. In Proceedings of the 5th International Conference on Information Processing in Sensor Networks, Nashville, TN, USA, 19–21 April 2006; pp. 2–10. 3. Soma, T.; Yoshida, Y. A generalization of submodular cover via the diminishing return property on the integer lattice. In Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems, Montreal, QC, Canada, 7–12 December 2015; pp. 847–855. 4. Cornuejols, G.; Fisher, M.; Nemhauser, G.L. On the uncapacitated location problem. Ann. Discret. Math. 1977,1, 163–177. 5. Nguyen, B.-N.T.; Pham, P.N.; Tran, L.H.; Pham, C.V.; Snášel, V. Fairness budget distribution for influence maximization in online social networks. In Proceedings of the International Conference on Artificial Intelligence and Big Data in Digital Era, Ho Chi Minh City, Vietnam, 18–19 December 2021; pp. 225–237. 6. Pham, C.V.; Thai, M.T.; Ha, D.; Ngo, D.Q.; Hoang, H.X. Time-critical viral marketing strategy with the competition on online social networks. In Proceedings of the International Conference on Computational Social Networks, Ho Chi Minh City, Vietnam, 2–4 August 2016; pp. 111–122. 7. Lin, H.; Bilmes, J. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Portland, OR, USA, 19–24 June 2011; pp. 510–520. 8. Agrawal, R.; Squires, C.; Yang, K.; Shanmugam, K.; Uhler, C. Abcd-strategy: Budgeted experimental design for targeted causal structure discovery. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, PMLR, Naha, Japan, 16–18 April 2019; pp. 3400–3409. 9. Das, A.; Kempe, D. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on Machine Learning, ICML, Bellevue, WA, USA, 28 June–2 July 2011; pp. 1057–1064. 10. Liu, S. A review for submodular optimization on machine scheduling problems. Complex. Approx. 2020,12000, 252–267. 11. Soma, T.; Yoshida, Y. Maximizing monotone submodular functions over the integer lattice. Math. Program. 2018 ,172, 539–563. [CrossRef] 12. Alon, N.; Gamzu, I.; Tennenholtz, M. Optimizing budget allocation among channels and influencers. In Proceedings of the 21st International Conference on World Wide Web, Lyon, France, 16–20 April 2012; pp. 381–388. 13. Soma, T.; Kakimura, N.; Inaba, K.; Kawarabayashi, K.-I. Optimal budget allocation: Theoretical guarantee and efficient algorithm. In Proceedings of the International Conference on Machine Learning, PMLR, Beijing, China, 21–26 June 2014; pp. 351–359. 14. Kapralov, M.; Post, I.; Vondrák, J. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the TwentyFourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, New Orleans, LA, USA, 6–8 January 2013; pp. 1216–1225. Mathematics 2022,10, 3772 18 of 19 15. Demaine, E.D.; Hajiaghayi, M.; Mahini, H.; Malec, D.L.; Raghavan, S.; Sawant, A.; Zadimoghadam, M. How to influence people with partial incentives. In Proceedings of the 23rd International Conference on World Wide Web, Seoul, Korea, 7–11 April 2014; pp. 937–948. 16. Bian, A.; Buhmann, J.; Krause, A.; Tschiatschek, S. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning, PMLR, Sydney, Australia, 6–11 August 2017; pp. 498–507. 17. Feldman, M.; Naor, J.; Schwartz, R. A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA, 22–25 October 2011; pp. 570–579. 18. Korula, N.; Mirrokni, V.; Zadimoghaddam, M. Online submodular welfare maximization: Greedy beats 1/2 in random order. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, Portland, OR, USA, 14–17 June 2015; pp. 889–898. 19. Ha, D.T.; Pham, C.V.; Hoang, H.X. Submodular Maximization Subject to a Knapsack Constraint Under Noise Models. Asia-Pac. J. Oper. Res. 2022, 2250013. [CrossRef] 20. Huang, C.; Kakimura, N. Multi-pass streaming algorithms for monotone submodular function maximization. Theory Comput. Syst. 2022,66, 354–394. [CrossRef] 21. Chekuri, C.; Gupta, S.; Quanrud, K. Streaming algorithms for submodular function maximization. Int. Colloq. Autom. Lang. Program. 2015,9134, 318–330. 22. Buschjäger, S.; Honysz, P.; Pfahler, L.; Morik, K. Very fast streaming submodular function maximization. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Bilbao, Spain, 13–17 September 2021; pp. 151–166. 23. Pham, C.; Pham, D.; Bui, B.; Nguyen, A. Minimum budget for misinformation detection in online social networks with provable guarantees. Optim. Lett. 2022,16, 515–544. [CrossRef] 24. Gu, S.; Shi, G.; Wu, W.; Lu, C. A fast double greedy algorithm for non-monotone dr-submodular function maximization. Discret. Math. Algorithms Appl. 2020,12, 2050007. [CrossRef] 25. Mitrovic, S.; Bogunovic, I.; Norouzi-Fard, A.; Tarnawski, J.; Cevher, V. Streaming robust submodular maximization: A partitioned thresholding approach. In Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, Long Beach, CA, USA, 4–9 December 2017; pp. 4557–4566. 26. Pham, C.; Vu, Q.; Ha, D.; Nguyen, T.; Le, N. Maximizing k-submodular functions under budget constraint: Applications and streaming algorithms. J. Comb. Optim. 2022,44, 723–751. [CrossRef] 27. Nguyen, B.; Pham, P.; Pham, C.; Su, A.; Snášel, V. Streaming Algorithm for Submodular Cover Problem Under Noise. In Proceedings of the 2021 RIVF International Conference on Computing and Communication Technologies (RIVF), Hanoi, Vietnam, 19–21 August 2021; pp. 1–6. 28. Gong, S.; Nong, Q.; Bao, S.; Fang, Q.; Du, D.-Z. A fast and deterministic algorithm for knapsack-constrained monotone dr-submodular maximization over an integer lattice. J. Glob. Optim. 2022, 1–24. [CrossRef] 29. Liu, B.; Chen, Z.; Du, H.W. Streaming algorithms for maximizing dr-submodular functions with d-knapsack constraints. In Proceedings of the Algorithmic Aspects in Information and Management—15th International Conference, AAIM, Virtual Event, 20–22 December 2021; Volume 13153, pp. 159–169. 30. Tan, J.; Zhang, D.; Zhang, H.; Zhang, Z. One-pass streaming algorithm for dr-submodular maximization with a knapsack constraint over the integer lattice. Comput. Electr. Eng. 2022,99, 107766. [CrossRef] 31. Zhang, Z.; Guo, L.; Wang, Y.; Xu, D.; Zhang, D. Streaming algorithms for maximizing monotone dr-submodular functions with a cardinality constraint on the integer lattice. Asia Pac. J. Oper. Res. 2021,38, 2140004:1–2140004:14. [CrossRef] 32. Kazemi, E.; Mitrovic, M.; Zadimoghaddam, M.; Lattanzi, S.; Karbasi, A. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In Proceedings of the 36th International Conference on Machine Learning, PMLR, Long Beach, CA, USA, 9–15 June 2019; Volume 97, pp. 3311–3320. 33. Nemhauser, G.L.; Wolsey, L.A.; Fisher, M.L. An analysis of approximations for maximizing submodular set functions—I. Math. Program. 1978,14, 265–294. [CrossRef] 34. Sviridenko, M. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 2004 ,32, 41–43. [CrossRef] 35. Cálinescu, G.; Chekuri, C.; Pxaxl, M.; Vondrxaxk, J. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J.Comput. 2011,40, 1740–1766. [CrossRef] 36. Badanidiyuru, A.; Vondrák, J. Fast algorithms for maximizing submodular functions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, SIAM, Portland, OR, USA, 5–7 January 2014; pp. 1497–1514. 37. Soma, T.; Yoshida, Y. Non-Monotone DR-Submodular Function Maximization. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, CA, USA, 4–9 February 2017; pp. 898–904. 38. Badanidiyuru, A.; Mirzasoleiman, B.; Karbasi, A.; Krause, A. Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’14, Association for Computing Machinery, New York, NY, USA, 24–27 August 2014; pp. 671–680. Mathematics 2022,10, 3772 19 of 19 39. Hatano, D.; Fukunaga, T.; Maehara, T.; Kawarabayashi, K. Lagrangian decomposition algorithm for allocating marketing channels. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, TX, USA, 25–30 January 2015; pp. 1144–1150. 40. Kunegis, J. KONECT: The koblenz network collection. In Proceedings of the 22nd International World Wide Web Conference, WWW’13, ACM, Rio de Janeiro, Brazil, 13–17 May 2013; pp. 1343–1350.