Submodular Maximization in Clean Linear Time
Authors: Wenxin Li
Moran Feldman
Ehsan Kazemi
Amin Karbasi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Submodular maximization
query complexity
cardinality constraint
Knapsack constraint
p-set system constraint
information-theoretic lower bound

Abstract: In this paper, we provide the first deterministic algorithm that achieves $1/2$-approximation for monotone submodular maximization subject to a knapsack constraint, while making a number of queries that scales only linearly with the size of the ground set $n$. Moreover, our result automatically paves the way for developing a linear-time deterministic algorithm that achieves the tight $1-1/e$ approximation guarantee for monotone submodular maximization under a cardinality (size) constraint. To complement our positive results, we also show strong information-theoretic lower bounds. More specifically, we show that when the maximum cardinality allowed for a solution is constant, no deterministic or randomized algorithm making a sub-linear number of function evaluations can guarantee any constant approximation ratio. Furthermore,  when the constraint allows the selection of a constant fraction of the ground set, we show that any algorithm making fewer than $\Omega(n/\log(n))$ function evaluations cannot perform better than an algorithm that simply outputs a uniformly random subset of the ground set of the right size. We extend our results to the general case of maximizing a monotone submodular function subject to the intersection of a $p$-set system and multiple knapsack constraints. Finally, we evaluate the performance of our algorithms on multiple real-life applications, including movie recommendation, location summarization, Twitter text summarization, and video summarization.

Submodular Maximization in Clean Linear Time
Wenxin Li
Moran Feldman University of Haifa moranf e@cs. haifa.ac... i1
The Ohio State University
1i 732883220sseee .du
Ehsan Kazemi Google @hsankazeemi@googgle com
Amin Karbasi
Yale University, Google Research amin. karbasi@yale edu.
Abstract
In this paper, we provide the first deterministic algorithm that achieves 1/2- approximation for monotone submodular maximization subject a knapsack con- straint, while making number of queries that scales only linearly with the size of the ground set n. Moreover, our result automatically paves way for developing a linear-time deterministic algorithm that achieves the tight - 1/e approxima- tion guarantee for monotone submodular maximization under a cardinality (size) constraint. To complement theoretic lower bounds. More specifically, we show that when the maximum car- dinality allowed for solution constant, no deterministic randomized algo- rithm making a sub-linear number of function evaluations can guarantee any con- stant approximation ratio. Furthermore, when the constraint allows the selection a constant fraction of the ground set, we show that any algorithm making fewer than M(n/ log(n)) function evaluations cannot perform better than algorithm that simply outputs a uniformly random subset of the ground set of the right size. of maximizing monotone submodu- lar function subject to the intersection of a p-set system and multiple knapsack constraints. Finally, we evaluate the performance of our algorithms on multiple real-life applications, including movie recommendation, location summarization, Twitter summarization, and video summarization.
positive results, also show strong information-
We extend our results to the general
Introduction
In the era of big data, one of the main challenges that we daily face make an informed decision while taking into account all the relevant information. The study of how to make such near-optimal decisions from massive pool of possibilities is the heart of combinatorial optimization. It well-known that without further structures, finding near-optimal solution for combinatorial opti- mization problem is notoriously hard, similar to finding global minimum of general non-convex function. Nevertheless, the problems of practical interest, such as the ones we encounter in machine learning applications, are often much more well-behaved which makes them amenable to (exact or approximate) optimization techniques.
One celebrated combinatorial structure is submodularity, also known as diminishing returns, stating that the added value of an element (e.g., image, sensor, etc.) to context (data set of images, sensor network, etc.) decreases as the context in which it considered grows. Submodular functions have attracted significant interest from the machine learning community, and have led to the development of algorithms with netr-optimal solutions for a wide range of applications, including outbreak de- tection [52], graph cuts in computer vision [40], image and video summarization [22, 32, 59, 70), active learning [19, 27, 28), compressed sensing and structured sparsity [3, 16), fairness machine
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

learning [13, 41], recommendation [60], human brain parcellation [64], model training [87, and learning causal structures [66. 75]. For recent surveys on the applications of submodular functions in machine learning and artificial intelligence, we refer the interested reader to [7, 69).
In their pioneering work, Nemhauser et al. [62] showed that greedy algorithm achieves tight 1/c approximation for maximizing a monotone submodular function subject to cardinality constraint (SMC). Running the greedy algorithm too expensive as it requires ((nk) function evaluations, where n is the size of the ground set and k is the maximum cardinality allowed by the constraint. Since then, there has been a significant effort to develop faster algorithms [12. 55, 72] and extend the approximation guarantee to more complex constraints (such as knapsack and p-set system) [4. 32].
In this work, propose the first deterministic linear time algorithm for maximizing monotone submodular function subject to a knapsack constraints (SMK), achieving (1/2 - E) apapproxinoaoonn using (n(n) function evaluations. We note that some nearly-linear time algorithms have been pre- viously proposed for this problem. Ene and Nguyen [18] showed such an algorithm achieving (1 1-1/e- -0 aapproxiimtai,,, but the number of function evaluation used by their algorithm scales poorly with (namely, (((1)))//))) which makes it impractical even for moderate values ef This has motivated Yaroslavtsev et al. [73] to design an algorithm called Greedy+ that achieve (1/2- s)- approximation and has much more practical nearly-linear time complexity. Nevertheless, our algorithm manages to combine the approximation guarantee of Greedy+ with a clean linear time. For the special case of a cardinality constraint, i.c., when the elements of the ground set have the same cost, our algorithm automatically reduces to a deterministic linear-time algorithm that guaran- tees (1 - 1/ee - E) approximation via (n(n) function evaluations. This special result has also been independently obtained by [46, 47]. Previously, the sfte-offthhe-ar deterministic algorithm only managed to achieve this approximation ratio using Oz (n log log n) function evaluations [36] (albeit in their new arXiv version, [38] claimed a linear-time algorithm, but with a worse dependence compared to our work).
Since the linear time complexity of our algorithm is the minimum required to read all the elements of the ground set, is difficult to believe that any algorithm can improve over it while guarantee- ing a reasonable approximation ratio. However, note that a single function evaluation can provide information about many elements of the ground set, and therefore, it is not a priori clear that an algorithm making sub-linear number of function evaluations may not exist (even if its total time complexity is linear). Nevertheless, we are able to prove that this is indeed the case in at least two important regimes. First, we show that when the maximum cardinality allowed for the solution is constant, no algorithm making a sub-linear number of function evaluations can guarantee any con- stant approximation ratio for SMC. Second, when the constraint allows the selection of a constant fraction of the ground set, we show that any algorithm making fewer than 12(n// (oo//))()))) function evaluations cannot perform better than an algorithm that simply outputs uniformly random subset of the ground set of the right size. Our technique also leads to a similar inapproximability result for unconstrained submodular maximization (USM). These lower bounds, along with the correspond- ing linear- tineartimee algorithms, nearly complete our understanding of the minimum query complexity of SMC, SMK, and USM problems. It is important to note that our inapproximability results are based on information theoretic arguments rather than relying on any complexity assumptions.
We consider the more general setting where we maximize monotone submodular function subject to a p-set system and dl knapsack constraints (SMKS). We study the trade-off between the time com- plexity and approximation ratio for this problem. In particular, our results improve over the state-of- the-art approximation for nearly-linear time algorithms [4]. Finally, we evaluate the performance of our algorithms using real-life and synthetic experiments, including movie recommendation, location summarization, vertex cover, twitter text summarization and video summarization.
1.1
Additional Related Work
The work of Badanidiyuru and Vondrák [4] is probably the first work whose main motivation was to find algorithms with guaranteed approximation ratios for submodular maximization problems that provably enjoy faster time complexities. This work introduced the thresholding technique, which became a central component of basically every fast deterministic implementation of the greedy algo- rithm considered to date, including our algorithms. In particular, using this technique, Badanidiyuru and Vondrák [4] described an On(n log n) time algorithm for maximizing a monotone submodular function subject to a cardinality constraint.
2

---

Sviridenko [67] was the first to obtain (1- approximaatinnnnnnn for maximizing a monotone sub- modular function subject to a knapsack constraint. Their original algorithm was very slow (having a time complexity of )nz²)), but it can be improved to run in Ö(n*) time using the thresholding technique of [4]. The algorithm of Sviridenko [67] is based on making 3 guesses. Recently, Feld- man et al. [24] showed that the optimal approximation ratio of 1 1/e can be obtained using only guesses, leading to Ö(n²)) time. They also showed that single guess suffices to guarantee a slightly worse approximation ratio of 0.6174 and requires only (n²)) time [24]. There exists also an impractical hearly-linear time algorithm for the problem due to [18]. Another fast algorithm was suggested by [4], but an error was later found in their analysis (see [18] for details). We also note that multiple recent works aimed to bound the performance of natural (and historically important) greedy al algorithm [24, 49, 68). A brief review on non-monotone submodular maximization subject to cardinality and knapsack constraints be found in Appendix A.
When considering fast algorithms, it is important to consider also (semi- >streaming algorithms since these algorithms usually naturally fast. Among the first semi-streaming algorithms for submod- ular maximization was the work of Badanidiyuru et al. [5], who obtained (1/2 - E) apapproximattion for SMC. While this work was later improved by Kazemi et al. [42] and extended non-monotone functions [1], it was also proved that no semi-streaming algorithm can provide a better than 1/2- approximation for this problem [23]. The more general case of a knapsack constraint was first considered in the semi-streaming setting by Yu et al. [74]. Improved algorithms for this problem were later found by [37, 39] for single pass and by [38, 73] for multiple passes.
Maximizing a monotone submodular function subject to a p-set system constraint was first studied by Fisher et al. [25]. who showed that a natural greedy algorithm obtains (p + 1) aappoopoooinntaioonn for this problem. Many years later, Badanidiyuru and Vondrák [4] used their thresholding technique to get nearly-linear time algorithm guarantecing (p + 2d + + =) =)- -appaoxxiimiaioonn even when there are d knapsack constraints (in addition to the p-set system constraint). Recently, Badanidiyuru et al. [6] presented new technique that allows them improve over the last approximation ratio. They explicitly consider the implications of their ideas only for the regime where d I p. and in this regime they achieve [2(p + 1+ =)] -a)===aaaprroxiaataaa approximmation and (p + 1 11++ E) -aprroximation in Ö(r /s) and ((n"r2/e) time, respectively, where S n. is the rank of p-set system. We note, however, that some of the ideas of [6] can also be applied the regime d > p. leading to (p + d + 1)-1 approximation in Ō(n²) time. One can observe that the improvement in the approximation ratio obtained by the new results of [6] comes at the cost of an increased time complexity. Our results in Section further study this trade-off between the time complexity and approximation ratio and improve over the state-of- sate-of-the-ae art approximation for nearly-linear time algorithms.
2 Notations and Preliminaries
set function f: 2A' - R over a ground set A is a function that assigns a numeric value to every subset of N. Given such a function, an element u E N and set S C N, we denote by f(u S) A S(S (u)) - S(S) the marginal contribution of u to S with respect to ʃ. The set function I is submodular if [(u S) Z J(u (T) for every two sets S C T C N and element E T, and it is monotone if [(u S) 2 0 for every element E N and set 5 C. All the set functions considered in this paper are also non-negative. Additionally, given two sets S,T E N, we define the shorthand f(T) S) 2 (T) - f(S). Furthermore, given a set S and element u, we often use S + u as a shorthand for S (u).
We assume throughout the paper that algorithms are able to access the objective function f only through a value oracle that given a set S C N returns f(S). This (standard) assumption allows us to prove inapproximability results that are based on information theoretic arguments, and therefore, are independent of any complexity assumptions.
A set system M is ordered pair (N, where A is a ground set and I is non-empty subset of 2 that obeys the following property: S C C W and T E I, then S also belongs to I. It is customary to refer to the sets of I as independent (and to sets that do not belong to I as dependent). A base of a set S C N is subset of 5 that is independent and is not included in any other set having
'To be more exact, to get the (p + d 1) approximation one has to apply the idea used in the proof of Theorem 8 of [6] to the (p + 2d 1 E) approximmation algorithm due to [4].
3

---

these properties. The set system M = (W.I) is called p-set system for an integer 2 if for every S N the ratio between the sizes of the largest base of S and the smallest base of S is at most p.
3 Knapsack Constraint
In this section we consider the Submodular Maximization subject to Knapsack Constraint problem (SMK). In this problem we are given a non-negative monotone submodular function f: 2 - R Ro0 a non-negative cost function c: .N + R20 and a budget B >> O. We say that set S S N is feasible if it obeys c(S) I B (where c(S) - Enes c(u)), and the objective of the problem is to find set maximizing f among all feasible sets S S N. For simplicity, we assume below that c(u) (0. B] for every element u E N and that B = 1. These assumptions are without loss of generality because (i) every element of N whose cost exceeds B can be simply removed, (ii) every element of N whose cost can be safely assumed to part of the optimal solution (f is monotone), and (iii) one can scale the costs to make the budget B equal to 1.
When the knapsack constraint of SMK happens to be simply a cardinality constraint, we get problem known as Submodular Maximization subject to Cardinality Constraint (SMC). Formally, in this problem we have an integer parameter 1 S k S n, and we are allowed to output any set whose size is at most k. One can observe that SMC is special case of SMK in which c(u) = 1/k for every element N.
The first step of our proposed solution to solve SMK and SMC problems is getting an estimate I of the value of an optimal solution (up to constant factor). We show how this can be done in Appendix B. algorithm of Badamidiyuru and Vondrák [4] that, unlike the original algorithm of [4], uses the estimate I' reduce the number of thresholds that need to be considered. In Section 3.2, by combining the threshold-gres -reeedy variant from Section 3.1 with a post-proessinng step, we show how achieve the state-of-the-ard algorithm for SMK. The theoretical guarantee of this algorithm is given by Theorem 3.1.
Then, in Section 3.1 we present a variant of the threshold-greet
Theorem 3.1. For every ε > O, there exists deterministic (1/2 - appppoxxinaaio algo- rithm for Submodular Mawimization subject to Knapsack Cons traint ( (SMK) that uses loge="loge=> time.
Complementary to our result for SMK, our proposed variant of the threshold-greedy algorithm leads to deterministic linear algorithm for SMC, which is given by the next theorem.
Theorem 3.2. For every E > O, there exists deterministic (1 - 1/e c) -)-approximation algo-
rithm for Submodular Manimization subject to a Cardinality Constraint (SMC) using O(n/E) time.
3.1 Fast Threshold Greedy Algorithm
In this section, we present Algorithm 1 variant of the threshold-greedy algorithm from [4]. Algorithm 1 uses r, our estimate of the optimal value (T is calculated by Algorithm 4 which is given in Appendix B). Algorithm 4 enables us to reduce the number of thresholds that needed to be considered. Specifically, Algorithm I considers an exponentially decreasing series of thresholds between 8a-1' and l'/e, where is parameter of the algorithm. For every threshold considered, the algorithm adds to its solution every element such that (i) adding the element to the solution does not violate feasibility, and (ii) the density of the element with respect to the current solution exceeds that threshold. In addition to the parameter a, Algorithm I gets quality control parameter E E (0, 1).
The time complexity of Algorithm is given by the next observation.
Observation 3.3. The time complexity of Algorithm is O log
Due to space constraints, the proof of this observation and the other proofs omitted from this section can be found in Appendix C.
Let be the value of when Algorithm terminated. We analyze the approximation ratio of Algo- rithm I by describing two lower bounds on the performance of this algorithm. The following lemma gives the simpler among these bounds. Its proof based on the observation that the elements of TV St were not added by Algorithm to its solution even during the outer loop's 's last iteration.

---

Algorithm 1: FAST THRESHOLD GREEDY(E,
Let (an estimate of the value of an optimal solution) the output of Algorithm 2 Let <- 8a T. h <- 0 and So f- Ø.
while - ()/
for every element E N do
u & Sh, d(u) + c(Sp) and [(]SS.) then c(u)
Let uh+1 t- u and Sh+1 t- Sh + 4141- Increase h by
Update x- 6)T
return Sh.
Lemma 3.4. For every set T S N, if max c(u) < 1 cS,)). then f(S:) > f(T) dT J(OPT). In particular, max,EOPT c(u) s 1 c(Si) implies f(Si) 2 (1 (1-1/e) ((PP))
The following lemma gives the other lower bound need the performance of Algorithm 1. The proof of this lemma based on the standard argument in greedy-like algorithms, namely, the observation that adding all the elements of 7 to solution increases the value of the solution to at least T, and therefore, at least one element
is good choice that the algorithm can choose.
Lemma 3.5. For every set Ø + T C N and integer S SL) [(5h+1)-119w) 2 min E) c(T) a S(OPT)) c(W6+1)
max.eT c(u) S 1 c(Sa), then
Using the last two lemmata we can prove the following theorem, which implies Theorem 3.2. In nutshell, the proof of this theorem uses Lemma 3,4 when the output of Algorithm has the maximum allowed cardinality, and Lemma 3.5 otherwise.
Theorem 3.6. If we choose a = then, for every (0, 1). Algorithm runs in O(n/e) time and guarantees (1 1/e appprooximaaio for SMC.
3.2 General Knapsack Constraint in Clean Linear Time
In this section we prove Theorem 3.1. We should point out that Algorithm by itself does not guarantee any constant approximation guarantee for general knapsack constraints. However, this can be fixed by using the post-processing step described by Algorithm Recall that Algorithm maintains a solution Ss that grows the algorithm progresses. The post-processing step takes O log e snapshots of this solution at various times during the execution of Algorithm 1, and then tries to augment each one of these snapshots with a single element.
Algorithm 2: FAST THRESHOLD GREEDY POST-PROCESSING(C)
Execute Algorithm with a = E Store all sets Sy, Si...., ., St produced by this execution.
2 for i [logite J1 do
Let S6) be the set S₃ for the maximal & value for which c(S²) S a(1 + +
there exists an element u E N such that c(u) < 1 -((((i) then
Let (t)) be an element maximizing f (u 5()) among all the elements obeying the condition the previous line.
Let S(i)+ +- ((3) + (0)
else Let S(0)+ +- 5(0)
return the set maximizing f in (St) U ((u) u ( 0 | logi E 1].
The time complexity Algorithm is given by the next observation.
"To see this, consider an input instance consisting of an element u of size 8 > 0, an additional element w of size 1 and a function f(S) = 26 - IS {u}l + IS n [wH. For small enough and values. Algorithm will pick the solution {u) of value 26 instead of the much more valuable solution {w) whose value L.
5

---

Observation 3.7. Algorithm 2 runs in O(ne='
log (ogg=!) time.
The rest of this section is devoted to analyzing the approximation ratio of Algorithm 2. Consider the inequality
f(5(++) < 1/2- S(OPT) 0A S logi+e e-
(1)
If this inequality does not hold for some integer i, then Algorithm 2 clearly obtains at least 1/2- approximation. Therefore, it remains to consider the case in which Inequality (1) applies for every integer 0 S i S logi-s e_!_ One can observe that this inequality implies that OPT is non-empty because f(S(0)) 2 [(Ø) by the monotonicity of f. and therefore, we can define to be an element of OT maximizing c(r). Additionally, we assume below that r is not the only element of OPT-if this assumption does not hold, then Algorithm 2 trivially returns an optimal solution.
Lemma 3.8. !f c(r) 2 1- - E, then f(S.)) 2 (1/2 - 8) S(OPT).
If ((tr) 1/2- ((OP), then the last lemma follows immediately since {r} is one of the sets considered for the output of Algorithm 2 on Line 8. Otherwise, we get that OPT {r} is a set with a lot of value taking very small part of the budget allowed, and the proof of Lemma 3.8 uses Lemmata 3.4 and 3.5 to argue that f(Se) is always large when such a set exists.
So far have proved that the approximation ratio of Algorithm 2 is least 1/2 - when either Inequality (1) is violated or e(r) 2 1 e. The following lemma proves that the same approxima- tion guarantee applies also when neither of these cases applies, which completes the proof of Theo-
rem 3. The proof of this lemma defines i, to be the maximal integer such that e(1+s) < 1-c(r), and h, to be the index for which Sr. = 5(6.). If hr = l, then the proof uses Lemma 3.4 to argue that (Se..) is large. Otherwise, the proof uses Lemma 3.5 to argue that +1) is large. -) S(OPT).
Lemma 399. If c(r) S 1 then Inequality (1) implies (S() 2 (1/2- E)
4 Information- Thhooretcc Inapproximability Results
In this section we present our inapproximability results. The first result that we show is inapprox- imability for SMC (see Section 3 for the definition of this problem) showing that, when the number of elements allowed in the solution is constant, one cannot obtain a constant approximation ratio for this problem using onn) value oracle queries.
Theorem 4.1. Any (possibly randomized) algorithm guaranteeing a-approximation (a E (0) for Submodular Maximization subject to a Cardinality Constraint (SMC) must use M (oonk)) (k) value oracle queries. In particular, this implies that the algorithm must make 22()) value oracle queries when a and i are constants.
See Appendix D for the proof of Theorem 4.1. Let now consider the approximability of SMC in a different regime allowing larger values of k. Specifically,, we consider the regime in which the ratio between and & is some constant B. In this regime one can obtain 3-approximation by simply outputting a uniformly random subset of A of size k (which requires no value oracle queries); thus, this regime cannot admit an extremely pessimistic inapproximability result like the given by Theorem 4.1. Nevertheless, the following theorem shows that improving over the above- meeteoee "casy" approximation guarantee requires mearly-linest query complexity.
Theorem 4.2. For any rational constant 8 E (0. 1) and constant e >> O, every (possibly randomized) algorithm guaranteeing approximation ratio of 3 E for instances of Submodular Mawimizatic subject to Cardinal i ty Cons traint obeying k Bn. must use M logg) value oracle queries. Moreover, this is true even when the function f of is guaranteed to be linear function.
We prove in Section E. a restricted version of Theorem 4.2 that applics only to deterministic algo- rithms. Then, Section E.2 extends the proof to randomized algorithms, which implies Theorem 4.2. Table 1 summarizes our knowledge about the number of value oracle queries necessary for obtaining various approximation guarantees for SMC.
Using the technique of Theorem 4.2, we can also prove another interesting result. In the Uncon- strained Submodular Muximization problem (USM), the input consists of a non-negative (not nec- essarily monotone) submodular function f: 2N - Rzo- The objective is to output a set S C W maximizing f. Our result for USM is given by the next theorem (proved in Appendix F). This theorem

---

Table 1: Number of value oracle queries that are required and sufficient to obtain any given ap- proximation ratio for Submodular Maximization subject to Cardinality Constraint (SMC). The variable should understood as an arbitrarily small constant.
Approximation Ratio
Query Complexity
Regime
Range
Can he obtained using O(n) queries by Theorem 3.2 Mirza- soleiman et al. [55], and requires (2(m) queries by Theorem 4.1,
le - 1/e s]
Constant lo
be obtained using (nn)) queries via brute force; Q(n)) queries are necessary by Theorem 4.1.
Exact solution
[1 - 1/e,
Can be obtained by outputting a uniformly random subset of the right size (0 queries).
[0,8]
Can obtained using O(n) queries by Theorem 3.2 or Mirza- soleiman et al. [55]; requires Q2 Tog queries by Theorem 4.2.
[8 1/e
k: 8n
1/e [1 - +,,
Obtained by Greedy using ((nk) queries [62]; requires I2( log queries by Theorem 4.2.
Requires exponentially many queries [61].
Table 2: Number of value oracle queries required and sufficient to obtain any given approximation ratio for Unconstrained Submodular Maximization (USM). The variable & should be under- stood as an arbitrarily small constant.
Approximation Ratio
Required Query Complexity
Sufficient Query Complexity
Range
An approximation ratio of 1/4 can be obtained by outputting uniformly random subset of [20].
00, 1/4
(
e,,
Q Tog
(Theorem 4.3)
Using the Double Greedy algorithm of Buchbinder et al. [11].
Requires an exponential number queries [20].
1/2 1,
nearly completes our understanding of the minimum query complexity necessary to obtain various approximation ratios for USM. See Table for more detail.
Theorem 4.3. For any constant O, any algorithm for Unconstrained Submodulor Mazimi- zation that guarantees an approximation ratio of 1/4 + E must use 52( log value oracle queries.
The necessity of the log n term in Theorems 4.2 and 4.3 is discussed in Appendix G. Specifically, we show in this appendix an algorithm that can be used solve (exactly) the hard problem underlying these theorems using (nz/ log n) oracle queries. This algorithm is not efficient in terms of its time complexity, but it shows that one cannot prove lower bound stronger than 12(n/ log n) for this problem based on information theoretic arguments alone.
5 Set System and Multiple Knapsacks Constraints
In this section we consider the Krupsacks and a Set System Constraint problem (SMKS). In this problem we are given non-negative monotone submodular function f: 2N + R20. a p-system 2 non-negative cost functions c; . + R>o (one function for every integer 1 < d) and d positive values B2, ... Ba Knapsack budgets. We say that set S C N is feasible if it is independent in M and also obeys (S) < B, for every 1 < < (where (S) 2 Epes (u))). The objective of the problem is to find set maximizing f among all feasible sets S N.
M = (N.Z),
Algorithm 3 is the basic version of our proposed solution for SMKS (in Appendix I.1 we explain how to make this basic algorithm nearly- Algorithm 3 gets two parameters. The first of

---

these parameters is an integer À 2 1. Elements that have value larger than À with respect to at least one function G; are considered big elements, and are stored in the of the algorithm. The other elements of V are considered small elements. The algorithm never considers any solution that includes both big and small elements. Instead, it creates one candidate solution SB from the big elements, and one candidate solution from the small elements, and then outputs the better among the two (technically, in some cases the algorithm outputs directly the candidate solution based on the small elements without comparing it to SB). The candidate solution SB is constructed using a procedure called BigEl ementsAlg that gets the set B as input and outputs a feasible set whose value is at least a f(OPT B), where is some value in (0, 1] and OPT is arbitrary optimal solution. At this point we ignore the implementation of BigElementsAlg and leave the value of a unspecified. These gaps are filled in Section H.3.
Most of Algorithm is devoted to constructing the candidate solution out of small elements, which we refer to as the "small elements solution". In the construction of this solution, Algorithm 3 uses its second parameter p 2 that intuitively should represent the density of the small elements of OPT The algorithm initializes the small elements solution to be empty, and then iteratively adds to it the element with the largest marginal contribution among the small elements that have two properties: (i) their addition to the solution does not make it dependent in M, and (ii) their density (the ratio between their marginal contribution and cost according to the linear constraints) is at least p. This process of growing the small elements solution ends because no additional elements can be added to the solution (in other words, no element has the two properties stated above). In this case the better among SB and the small elements solution obtained Sg is returned. The other way in which the process of growing the small elements solution end is when it starts violating at least one linear constraint. When this happens, Algorithm uses a procedure called SetExtract (see Algorithm 7 in Section H.1) to get subset of the small elements solution that feasible and also has good value, and this subset returned.
end in ways. One option is that the process
Algorithm 3 assumes access to an estimate P of the density of the small elements of an optimal solution for the problem. In Section H.2 we explain how the dependence of the algorithm on p can be dropped without increasing the time complexity of the algorithm by too much. Recall that Section 1.1 demonstrated a trade-off between the time complexity and approximation guarantee of state-of-the -hce-----thh-rttt algorithms for SMKS. The next thcorem further studies this trade-off, and in particular, improves over the state-of-the-art approximation for nearly-lines time algorithms. The Ô notation in this theorem suppresses factors that are voly-logarithmn in d and g-l. Due to space constraints, the proof of Theorem 1 is differed to Appendix H.
Theorem 5.1. For every O, there exist algorithms that achieve [(1 + (())) + 1+ -1 approximation and (p + 1.5556 + y + e)-1 for Submodular Manimization subject to Knapsacks and a Set System Constraint in Ö(nd (n/d) and Ö(n² +nd) time, respectively.
Algorithm 3: Basic Algorithm(X,p)
// Build the set of big elements, and find a solution based on them. Let B + {u E N' Bisiga x
2 Let Sg be the output set of BigEllementsAl((B)
11 Construct a solution from the small elements.
Let So Ø. k + 0.
while there exists an element EN (Sk U B) such that Sy. + E I and
[uul Sk) p. (u) do Let U 1 be an element maximizing (u S&)) among all the elements obeying the condition of the loop.
Let Sk+1 + S& + Uk+1.
7 m'maaiiis (, S then Increase & by 1. else return the output set of SetExtract(A, Sk+1).
return the better set among Sg and St.
8

---

6 Experimental Results
We have studied the submodular maximization problem subject different constraints. In this sec- tion, we compare our proposed algorithms with the state-of-the-arr algorithms under the following constraints: (i) carnality constraint (Section 6.1), (ii) single knapsack constraint (Section 6.2), and (iii) combination of p-system and d knapsack constraints (Appendix J.4).
6.1 Cardinally Constraint
Cardinality constraint is the most widely studied setup in the submodular maximization literature. We compare our algorithm, FASTTHRESHOL. DOR.EEEDD (abbreviated as FTG) with LAZYGREFDY and NooSTRATIO [46] under cardinality constraint. LAZYGREEDY is an efficient implementation of the naive GREEDY algorithm in which the diminishing returns property of submodular functions is used to avoid oracle queries that are known to provide little gain [55]. It is well-known that LAZYGREEDY leads to several orders of magnitude speedups over GREEDY in practice.
In our first experiment, we implement a movie recommender system by finding diverse set of movies for a user. We adopt the approach of Lindgren et al. [54] to extract features for each movie by using ratings from the MovieLens dataset [31]. For a given set of movies N (IW1 n), let vector et represents the attributes of the i-th movie. The similarity matrix Mnxn between movies defined by Mij e *r,,,)( where dist( U; vi)) the euclidean distance between vectors De 2y E .N.. For this application, we used the following monotone and submodular function to quantify the diversity of given set of movies S: f(S) log matrix and Ms is a square sub-matrix of M consisting of the rows and columns corresponding to the movies the set S. Our objective is to maximize / under a cardinality constraint In Figure aa, we compare the utility of the algorithms on this instance. We observe that FAST &GREED with E {0.1, 0.2) performs as good as LAZYGREEDY, and BOOSTR ATIO performs slightly worse. is significantly
where is the identity
In Figure 1b, observe that the query complexity of less than that of LAZYGREEDY. It is interesting to note that, as is guaranteed by our theoretical results, the number of oracle calls for FASTTURESHOLDGREEDD is (almost) not increasing with k. In our second experiment, which appears in Appendix J.1, we consider a location summarization application and show that similar conclusions apply also to this application.
STOCHASTICGREEDY is a fast but randomized approach for solving SNC [55]. In Appendix J.2 we present an experiment comparing WASTTHRESHOLLDDRRDDY with STOCHASTICGREED un- der the cardinality constraint a vertex cover context. In general, this experiment shows that is significantly better than that of STOCHASTICGREEDY, the utility of HRSTTHRESHOU.DDC sometimes also outperforms STOCHASTICGREEDY in terms and that WEATTHRREHHLLDDGEEEEEE
of the query complexity. We also observe high variability in the utility of solutions returned by SToCHASTICGREEDY which diminishes the benefit from this algorithm.
6.2 Single Knapsack Constraint
In this section, we evaluate the performance of Algorithm 2 (referred to as FTGP) with that of DYNAMICMRT [37] and DENSITY DENSITYGREEDY under single knapsack constraint. DENSITYGREED greedily adds elements that maximize the ratio between their marginal gain and knapsack cost (but ignoring elements whose addition will result in a violation of the knapsack constraint). In our first experiment for this constraint, we again consider the movie recommendation application from Section 6. The cost of each movie is defined to be proportional to the absolute difference between the rating of that movie and 10 (the maximum rating in iMDB). In this application, the goal is to find diverse set of movies while guaranteeing that the total rating of the picked movies is high enough [6]. From Figures Ic and dd, we observe that Algorithm 2 significantly outperforms the other two algorithms with respect to both the utility and number of oracle calls metries. For our second experiment under the knapsack constraint, which appears in Appendix J.3, we consider Twitter text summarization. In this experiment we again get that Algorithm 2 surpasses the baseline algorithms.
7 Conclusion and Societal Impact
An algorithm for maximizing a submodular function is conventionally measured in terms of two quantities: a) approximation guarantee, i.e., how well performs with respect to the (exponential time) optimum algorithm, and b) query complexity, i.e., how many function evaluations it requires.

---

80
14000
FTG (e 6/2
Number of Oranle Calls
60
Cooaly
Doot Zaiio
10000
Objerzvv
8000
6000
0-
50
100
150
Cardinality
Cardinaity k
(a)
(b)
Number of Oracle Caalls
109-
Objective value
300
DysarscMRT 0.5)
DynmeckRt (s (.))
Donwirs Gredy
Brasly Groely
200
100
0.6
0.8
1.0
0.2
0.4
Knapsack Capacity
Knapsack Capucity
(c)
(d)
Figure 1: Movie Recommendation: (a) and (b) compare FASTTURESSIOLLDGREDYY (referred to FTG) with LAZYGREEDY and BOOSTRATIO [46] under cardinality constraint; (c) and (d) compare Algorithm 2 (referred to as FTGP) with DYNAMICMRT [37] and DENSITYGREEDY under single knapsack constraint.
In their seminal work, Nemhauser and Wolsey [61] and Nemhauser et al. [62] resolved part (a). In this paper, after 44 years and building large body of prior work, nearly resolved part (b) and portrayed a nearly complete picture of the landscape. Specifically, we developed a clean linear- time algorithm for maximizing monotone submodular function subject cardinality constraint (and more generally a knapsack constraint). We also provided information-theorrtie lower bounds on the query complexity of both constrained and unconstrained (non-monotone) submodular max- imization. Finally. we studied the trade-off between the time complexity and approximation ratio for maximizing a monotone submodular function subject to p-system and d knapsack constraints. This work does not have any negative societal impact.
Like most algorithms in the literature, algorithms assume the ability exactly evaluate the objective function. In some applications exact evaluations is too costly, which has motivated works (such as [33)) that considered erroneous value oracles. Extending our work in this direction is an interesting question for future research.
Funding Transparency Statement
Funding in direct support this work: The work of Moran Feldman was supported in part by Israel Science Foundation (ISF) grant no. 459/20. The work of Amin Karbasi was supported in part by the NSF (ISS 1845085,,32), ONR (N00014- 19-1-2406), and the AT Institute for Leaaring--Enabled Optimization at Scale (TILOS).
10

---

References
[1] Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal streaming algorithms for submodular maximization with cardinality constraints. In International Collo- quium on Automata, Languages, and Programming (ICALP), volume 168, pages 6:1-6:19, 2020.
[2] Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiff- enhäuser. Fast adaptive non-monotone submodular maximization subject to a knapsack con- straint. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[3] Francis R Bach. Structured sparsity-inducing norms through submodular functions. In Ad- vances in Neural Information Processing Systems (NeurIPS), pages 118-126, 2010.
[4] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In ACM SCM-SIMM Symposium on Discrete Algorithms (SODA), pages 1497-1514, 2014.
[5] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause, Streaming submodular maximization: massive data summarization on the fly. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 671-680. ACM, 2014.
[6] Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, and Jan Vondrák, Submodular Maximization Through Barrier Functions. In Advances in Neural Information Processing Sys- tems (NeurIPS), 2020.
[7] Jeff Bilmes. Submodularity in machine learning and artificial intelligence. CoRR, abs/2202.00132,, 2022.
[8] Niv Buchbinder and Moran Feldman. Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms, 14())32: 2018
[9] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via nonsym- metric technique. Math. Oper: Res., 44(3):988- 1005, 2019.
[10] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization Symposium Discrete Algorithmss (SODA), pages
with cardinality constraints. In
1433-1452, 2014.
[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, and Roy Schwartz. Comparing apples and oranges: Query trade-off in submodular maximization. Math. Oper. Res., 42(2): 309- 2017.
[13] L. Elisa Celis, Amit Deshpande, Tarun Kathuria, and Nisheeth K. Vishnoi. How to be Fair and Diverse? CoRR, abs/ abss/610..01888 10000 2016.
[14] Vasek Chvátal. The tail of the hypergeometric distribution. Discret. Math., 25(3):285-287, 1979.
[15] Sandra Eliza Fontes De Avila, Ana Paula Brandão Lopes, Antonio da Luz Jr, and Amaldo de Albuquerque Araújo. Vsumm: A mechanism designed to produce static video summaries and novel evaluation method. Pattern Recognition Letters, 32(1):56-68, 2011.
[16] Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(6B):353933668 2018.
[17) Alina Ene and Huy L. Nguyen. Constrained submodular maximization: Beyond 1/e. In Foun- dations of Computer Science (FOCS), pages 248-257, 2016.
[18] Alina Ene and Huy L. Nguyen. A nearly-linear time algorithm for submodular maximiza- tion with a knapsack constraint. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 53:1-53:12, 2019.
[19] Hossein Esfandiari, Amin Karbasi, and Vahab Mirrokni. Adaptivity in adaptive submodularity. In Conference on Learning Theory (COLT), pages 1823-1846. PMLR, 2021.
[20] Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM J. Comput., 40(4): 133-)11133-113,, 2011.

---

[21]
Moran Feldman. Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Foundations of Computer Science (FOCS), pages 570-579, 2011.
[22] Moran Feldman, Amin Karbasi, and Ehsan Kazemi. Do less, get more: Streaming submod- ular maximization with subsampling. Advances in Neural Information Processing Systems (NeurlPS), 31, 2018.
[23] Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications streaming and robustness. In ACM Symposium on Theory of Computing (STOC), pages 1363-1374. ACM, 2020.
[24] Moran Feldman, Zeev Nutov, and Elad Shoham. Practical budgeted submodular maximization. CoRR, abs/2007.04937, 2020.
[25] Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey. An analysis of approx- imations for maximizing submodular functions-II. Mathematical Programming Study, 8, 1978.
[26] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1098-1116, 2011.
[27] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42: 427-486, 2011.
[28] Andrew Guillory and Jeff Bilmes. Interactive Submodular Set Cover. In International Confer-
ence on Machine Learning. pages 415-422. Omnipress, 2010.
[29] Ran Haba, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. Streaming submodular max- imization under k-set system constraint. In International Conference on Machine Learning (ICML), pages 3939-3949. PMLR, 2020.
[30] Kai Han, Shuang Cui, Tianshuai Zhu, Enpei Zhang, Benwei Wu, Zhizhuo Yin, Tong Xu, Shaojic Tang, and He Huang, Approximation algorithms for submodular data summarization with a knapsack constraint. In International Conference on Measurement and Modeling of Computer Systems, pages 65-66, 2021.
[31] F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm Transactions on Interactive Intelligent Systems (TIIS), 5(4: 2015.
[32] Christopher Harshaw, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. The power of sub- sampling in submodular maximization. Mathematics of Operations Research, 2021.
[33] Avinatan Hassidim and Yaron Singer. Submodular optimization under noise. In Conference on Learning Theory (COLT), pages 1069- 1122, 2017.
[34] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[35] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
[36] Chien-Chung Huang and Naonori Kakimura. Multi-pass pass streaming algorithms for monotone submodular function maximization. CoRR, abs/ 802.062 12, 2018
[37] Chien-Chung Huang and Naonori Kakimura. Improved streaming algorithms for maximizing monotone submodular functions under knapsack constraint. Algorithmica, 83(3):879-902, 2021.
[38] Chien-Chung Huang and Naonori Kakimura. Multi-pass streaming algorithms for monotone submodular function maximization. Theory Compur. Syst., 66(1):354-33) 394,, 2022.
[39] Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. Streaming algorithms for max- imizing monotone submodular functions under a knapsack constraint. Algorithmica, 82(4): 1006-1032, 2020.
[40] Stefanie Jegelka and Jeff Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. Computer Vision and Puttern Recognition (CVPR), pages 1897-1904. IEFE, 2011.
12

---

[41] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust sub- modular maximization: Data summarization with privacy and fairness constraints. In Interna- lional conference on machine learning (ICML), pages 2544-2553 PMLR, 2018.
[42] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adap- tive complexity. In International Conference on Machine Learning (ICML), pages 3311-3320.
PMLR, 2019.
[43] Ehsan Kazemi, Shervin Minace, Moran Feldman, and Amin Karbasi. Regularized submodular maximization at scale. In International Conference Machine Learning (ICML), pages 5356- 5366. PMLR, 2021.
[44] Andreas Krause and Daniel Golovin. Submodular Function Maximization. In Tractability: Practical Approackes to Hard Problems. Cambridge University Press, 2012.
[45] Alan Kuhnle. Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In Advances in Neural Information Processing Systems (NeurIPS), pages 2371- 1- 2381, 2019.
[46] Alan Kuhnle. Quick streaming algorithms for maximization of monotone submodular func- tions in linear time. In AISTATS, volume 130 of Proceedings of Machine Learning Research, pages 1360-1368. PMLR, 2021.
[47] Alan Kuhnle. Personal communication, 2022.
[48] Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmono- tone submodular maximization with knapsack constraints. Math. Oper. Res., 38(4):729-739, 2013.
[49] Ariel Kulik, Roy Schwartz, and Hadas Shachnai. A faster tight approximation for submodular maximization subject to a knapsack constraint. CoRR, abs/2102.12879) 2021.
[50] Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Maximizing non- monotone submodular functions under matroid knapsack constraints. SIAM J. Discret. Math., 23(4):2053-2277 2010.
[51] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http:://ssaap.saaaf.. edu/data, June 2014.
[52] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), pages 420-429 ACM, 2007.
[53] Vsevolod F. Lev and Raphael Yuster. On the size of dissociated bases. The Electronic Journal of Combinatories, 18(1), 2011.
[54] Erik M Lindgren, Shanshan Wu, and Alexandros G Dimakis. Sparse and greedy: Sparsifying submodular facility location problems. In NeulPS Workshop on Optimization for Machine Learning. 2015.
[55] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and An- dreas Krause. Lazier than lazy greedy. In Blai Bonet and Sven Koenig, editors, Conference on Artificial Intelligence (AAAI), pages 1812-1818. AAAI Press, 2015.
[56] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning (ICML), pages 1358-1367, 1367, 2016.
[57] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submod- ular maximization. The Journal of Machine Learning Research, 17(1):833-8832 2016.
[58] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning (ICML), pages 6950-6960. PMLR, 2020.
[59] Marko Mitrovic, Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Data summa- rization at scale: A two-stage submodular approach. International Conference on Machine Learning (ICML) pages 3596-3605. PMLR, 2018.
13

---

[60] Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause, and Amin Karbasi. Adap- tive sequence submodularity, Advances Neural Information Processing Systems (NeurIPS), 32, 2019.
[61] G. L.. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematicy of Operations Research, 3(3):177-188, 1978.
[62] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maxi- mizing submodular set functions-I. Mathematical Programming. 14:265-294 1978.
[63] Shinsaku Sakaue. Guarantees of stochastic greedy algorithms for non-monotone submodular maximization with cardinality constraint. In International Conference on Artificial Intelligence and Statistics, (AISTATS), pages 11 11-21, 2020.
[64] Mehraveh Salehi, Amin Karbasi, Dustin Scheinost, and R Todd Constable. A submodular approach to create individualized parcellations of the human brain. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 478-485. Springer, 2017.
[65] Matthew Skala. Hypergeometric tail inequalities: ending the insanity. CoRR, 1311.5939, 2013.
[66] Scott Sussex, Caroline Uhler, and Andreas Krause. Near-optimal multi-perturbation experi- mental design for causal structure learning. Advances in Neural Information Processing Sys- tems (NeurIPS), 34, 2021.
[67] Maxim Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Oper. Res. Lett. 32(1):41 1311114332200 2004.
[68] Jing Tang. Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, and Junsong Yuan. Re- visiting modified greedy algorithm for monotone submodular maximization with a knapsack constraint. Proc. ACM Meas. Anal. Comput. Syst., 5(1):08:1 2021.
[69] Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, and Amin Kar- basi. Submodularity action: From machine learning to signal processing applications. IEEE Signal Processing Magazine, 37(55:120-133 2020.
[70] Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. Advances in Neural Informa- lion Processing Systems (NeurIPS), 2014.
[71] Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM J. Comput., 42(1):655-334 2013.
[72] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Fast multi-stage submodular maximization. In Inter- national conference on machine learning (ICML), pages 1494-1502. PMLR, 2014.
[73] Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. "bring your own greedy" Near-optimal 1/2-approximation for submodular knapsack. In International Conference Artificial Intelligence and Statistics (AISTATS), pages 3263-3274, 2020.
[74] Qilian Yu, Easton Li Xu, and Shuguang Cui. Streaming algorithms for news and scientific literature I recommendation: Monotone submodular maximization with a d-knapsack constraint.
IEEE Access, 1553736-53747 2018.
[75] Yuxun Zhou and Costas J Spanos. Causal meets submodular: Subset selection with directed information. In Advances in Neural Information Processing Systems (NeurIPS), pages 2649- 2657, 2016.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] There is
no risk of negative societal impacts form our work as we only solve the previously well-studied set of problems faster.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e-g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [Yes] It is not applicable.
5. If you used crowdsoureing conducted research with human subjects...
(a) It is not applicable.
15


Reviews:
[{"review_id": "vySq3fdPtQV", "reviewer": "Reviewer_FKqZ", "summary": "In this submission, the problem of maximizing a submodular function subject to a knapsack constraint is considered, where the function is accessed by an oracle. There is a lot of literature on this problem and several approximation algorithms are known. In this paper, an approximation algorithm with a guarantee of 1/2-eps is developed whose running time is linear in n. This does not improve the best previously known approximation factor (which is 1-1/e) but it is the first algorithm with this approximation factor that runs in linear time. For the special case of a cardinality constraint the factor improves to 1-1/e-eps. \n\nThe algorithmic result is complemented by information-theoretic lower bounds. It is shown that a linear number of function evaluations are needed to obtain a constant approximation guarantee even in the case of a cardinality constraint. This lower bound is true if the number k of allowed elements is constant. If it is a constant fraction of the size n of the ground set then Omega(n/log(n)) function evaluations are shown to be necessary to achieve a constant approximation.\n\nThe theoretical results are supported by experimental results showing that the designed approximation algorithm outperforms baseline algorithms from the literature.", "questions": "l 40: \"submodualr\" -> \"submodular\"\nl 50: \"makes is impractical\" -> \"makes is impractical\"\nl 130: definition of f(T|S): I think f(T) should be f(S).\nl 183: \"where\" -> \"were\"\npage 15, last line: \"forall e in ...\" -> \"forall u in\"", "limitations": "n.a.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The algorithm is very clean and natural and the proof of the approximation guarantee is easy to follow. I very much enjoyed reading this part of the submission. However, this part is also close to existing literature and many ideas in this part are taken from existing literature. A weakpoint is, of course, that the approximation ratio is only 1/2-eps and not 1-1/e-eps (which is known to be achievable in polynomial time). The lower bounds are rather involved but quite interesting. The experiments are clearly not the main focus of the submission and I would rather see them as a proof of concept that the algorithm works in practice but not as a thorough evaluation. For example, the two baselines are natural but it is never argued why exactly these algorithms are chosen as baselines and not other algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dv9bV3YVHgg", "reviewer": "Reviewer_Z74k", "summary": "The authors of this paper propose a linear-time algorithm for maximizing monotone and submodular functions under knapsack constraints. The proposed algorithm extends the threshold-greedy algorithm for cardinality constraints. Besides the theoretical results, the authors also provide experimental results to demonstrate the advantages of the proposed algorithm compared to SOTA algorithms.", "questions": "Is the DENSITYGREEDY algorithm in experiments also accelerated by the Lazy Greedy idea?", "limitations": "1. This paper discusses the situation of minimizing the number of queries to the objective function. In many important applications of submodular optimization, such as influence maximization, we may first generate a sketch data structure that can well approximate the objective function and evaluating the approximate function value is not that computational expensive. It would be better if the authors could discuss something about this in Conclusion.\n2. One another interesting point is that the objective submodular function is often hard to compute exactly. What if we only have a noisy oracle of the function value? Is the proposed algorithm robust to a noisy oracle?\n3. A minor issue. After Observation 3.3, the authors say \"Let l be the value of k\". I guess here \"k\" should be \"h\" since there is no parameter k in Algorithm 1.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The proposed algorithm has linear time complexity and a strong approximation ratio.\n2. The authors also provide strong information-theoretic lower bounds for the problem studied in this paper.\n3. The authors conduct experiments on real-world datasets to show the practical advantages of the proposed algorithm to SOTA algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WmgYNX_nnyv", "reviewer": "Reviewer_d5nd", "summary": "The paper studies the problem of submodular maximization under cardinality/knapsack constraints and provides fast $\\mathit{deterministic}$ algorithm for the problem. The submodular maximization problem is a well-studied problem, where a set function $f$ defined over a ground set of n element, the set function is assumed to monotone and submodular (i.e., $f(A \\cup \\{u\\} - f(A) \\geq f(B \\cup \\{u\\}) - f(B)$ for any set $A\\subseteq B \\subseteq [n]$ and element $\\{u\\}$). The goal is to maximize the function value, for cardinality constraints, the algorithm is allowed to select up to k elements, while for knapsack constraints, the algorithm is allowed to select ground set element with a knapsack constraints (each element is associated with some cost).\n\nTo summarize, the paper designs deterministic algorithm that achieves\n\n(1) Under a knapsack constraint, it achieves $(1/2 -\\epsilon)$ approximation in $O(n\\epsilon^{-1}\\log(1/\\epsilon))$ times. The approximation ratio is not the state of art, as mentioned in the paper, as [Ene and Nguyen ICALP'19] proves a $(1-1/e -\\epsilon)$  approximation algorithm, with linear time, but the dependency on $\\epsilon$ is bad, i.e., $O((1/\\epsilon)^{\\epsilon})$.\n\n(2) Under cardinality constraints, it achieves $(1-1/e-\\epsilon)$-approximation using $O(n/\\epsilon)$ oracles. The approximation ratio is optimal, but the stochastic greedy algorithm (a randomized algorithm) has better oracle complexity of $O(n\\log(1/\\epsilon))$. A nearly lower bound is also proved in the paper (but I am not sure whether these are folklores...)\n\n(3) Constant approximation under multiple knapsack constraints.\n\n(4) Extensive experiments showing the effectiveness of the algorithm\n\nFrom a technical perspective, the algorithm is based on greedy algorithm with decreasing threshold. While for knapsack constraints, post processing is needed.\n\n\n\n---------------------- Post rebuttal ------------------\nAfter a few rounds of discussion with the author, I believe I convince the author that my main concern is (1) the significance of lower bound (I still believe it is more like a folklore result, but nice effort to write it down) and (2) the deterministic algorithm provides in the paper is not so exciting for an acceptance (I understand there are two or three paper in the area to develop deterministic algorithm).\n\n\n", "questions": "In line 365--366, it is claimed that the paper fully resolve the landscape of oracle complexity of submodular maximization, it seems too strong for me. After all, only deterministic algorithm is considered in this paper.", "limitations": "no", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength. The algorithm presents state of art $\\mathit{deterministic}$ algorithm for the classic problem of submodular maximization with cardinality constraints and a knapsack constraint. The experiments show the algorithm is practical, which is very nice!\n\n\nWeakness. There is no reason one restricts to deterministic instead of randomize algorithm, this decreases the value of the paper a lot.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P2OTBF6SFf", "reviewer": "Reviewer_QGLr", "summary": "The paper studies (mainly monotone) submodular maximization subject to various types of constraints. In particular, the authors focus is on deterministic algorithms that achieve constant factor approximation to the optimal solution while needing only linear time to terminate. \n\nThe main contributions of the paper are: \n- a deterministic $(1-1/e-\\varepsilon)$ approximation algorithm for monotone submodular maximization subject to cardinality constraint with $O(n/\\varepsilon)$ running time\n- a deterministic $(\\frac 12 - \\varepsilon)$ approximation algorithm for monotone submodular maximization subject to knapsack constraint with $O(n/\\varepsilon \\log(\\frac{1}{\\varepsilon}))$ running time\n\nTo complement these positive results, the authors construct information theoretical lower bounds that show how $\\tilde\\Omega(n)$ running time is needed to get constant factor approx for monotone submodular maximization with cardinality constraint and unconstrained non-monotone submodular maximization. For the former problem, it is also shown that when k is of the order of n, then no algorithm can do better than random sampling. \n\nFinally, the authors extend their techniques and design fast algorithms for monotone submodular maximization with a very general class of constraints, namely set system and multiple knapsack constraints. \n", "questions": "In the experiments with knapsack, is density greedy implemented with lazy updates? If not, why? Using lazy updates brings the computational complexity from $O(n^2)$ to $O(n \\log n)$", "limitations": "Other comments to the authors: \n- please, state from the abstract that the positive results only apply to monotone objectives\n- line 40 is submodular and not submodualr\n- please mention in the preliminary that you are considering the value oracle model\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Achieving fast algorithms for submodular optimization is a rich and exciting line of research motivated by the applications and it is definitely within the scope of the conference.\n\nAs it is common in submodular maximization, many of the techniques used in this work are a careful combination of well known ideas and I do not think this is a limit of the paper. I particularly like Algorithm 4: although simple, it is crucial to argue that a constant number of thresholds is enough and I think it can be used in many other contexts. To the best of my knowledge it is original, but I might be mistaken. I also like the lower bounds: they are not surprising, but I am pretty sure they will be cited in future works. \n\nOn the negative side, the actual contribution of the paper seems a bit marginal. Linear time algorithms (although randomized) already exists for cardinality constraints, while for knapsack it is easy to see that a straightforward algorithm like density greedy + lazy updates already yields a constant factor approximation in O(n log n) iterations, so the improvement consists in shaving the extra log factor.\n\nAlthough I have not checked in detail all the proofs, the claims are well supported. The paper is fairly well written and clear.\n\nThe related work section is very rich. I would just mention that the authors might want to spend some words on the case of non monotone objectives, for cardinality constraint see e.g. Kuhnle AAAI21, while for knapsack see Amanatidis et al. NeurIPS 20.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept