Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization

Authors: yixin  chen
ankur  nath
chunli  peng
alan  kuhnle
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:15:57

Abstract: For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than $1/e$ require continuous ideas, such as queries to the multilinear extension of a submodular function and its gradient, which are typically expensive to simulate with the original set function. For combinatorial algorithms, the best known approximation ratios for both size and matroid constraint are obtained by a simple randomized greedy algorithm of Buchbinder et al. [9]: $1/e \approx 0.367$ for size constraint and $0.281$ for the matroid constraint in $\mathcal O (kn)$ queries, where $k$ is the rank of the matroid. In this work, we develop the first combinatorial algorithms to break the $1/e$ barrier: we obtain approximation ratio of $0.385$ in $\mathcal O (kn)$ queries to the submodular set function for size constraint, and $0.305$ for a general matroid constraint. These are achieved by guiding the randomized greedy algorithm with a fast local search algorithm. Further, we develop deterministic versions of these algorithms, maintaining the same ratio and asymptotic time complexity. Finally, we develop a deterministic, nearly linear time algorithm with ratio $0.377$.

Main paper: 
 introduction: 
 A nonnegative set function f : 2 U → R + is submodular iff for all S ⊆ T ⊆ U, x ∈ U \ T , f (S ∪ {x})-f (S) ≥ f (T ∪ {x})-f (T ); and f is monotone iff f (S) ≤ f (T ) for all S ⊆ T ⊆ U. Submodular optimization plays an important role in data science and machine learning [3] , particularly in tasks that involve selecting a representative subset of data or features. Its diminishing returns property makes it ideal for scenarios where the incremental benefit of adding an element to a set decreases as the set grows. Applications include sensor placement for environmental monitoring [19, 27] , where the goal is to maximize coverage with limited sensors, feature selection [22, 18, 2] in machine learning to improve model performance and reduce overfitting, and data summarization [23, 31] for creating concise and informative summaries of large datasets. Further, many of these applications employ submodular objective functions that are non-monotone, e.g. Mirzasoleiman et al. [23] , Tschiatschek et al. [31] . Formally, we study the optimization problem (SM): max f (S) , s.t. S ∈ I, where f is nonnegative, submodular and not necessarily monotone; and I ⊆ 2 U is a family of feasible subsets. Specifically, we consider two cases: when I is a size constraint (all sets of size at most k); and more generally, when I is an arbitrary matroid of rank k.In this field, algorithms typically assume access to a value oracle for the submodular function f , and the efficiency of an algorithm is measured by the number of queries to the oracle, because evaluation of the submodular function is typically expensive and dominates other parts of the computation. In the general, not necessarily monotone case, the approximability of constrained submodular optimization in the value oracle model is not well understood. For several years, 1/e ≈ 0.367 was conjectured 38th Conference on Neural Information Processing Systems (NeurIPS 2024).Table 1 : The prior state-of-the-art and the ratios achieved in this paper, in each category: deterministic (det), randomized combinatorial (cmb), and continuous (cts).Reference Query Ratio Type Size Buchbinder and Feldman [5] O k 3 n 1/e ≈ 0.367 Det Buchbinder et al. [9] O (kn) 1/e Cmb Buchbinder and Feldman [7] poly to be the best ratio, as this ratio is obtained by the measured continuous greedy [15] algorithm that also gets the 1 -1/e ratio in the monotone setting, which is known to be optimal [24] . However, in several landmark works, the 1/e barrier was broken: first to 0.371 by Buchbinder et al. [9] (for size constraint only) and subsequently to 0.372 by Ene and Nguyen [13] , then 0.385 by Buchbinder and Feldman [6] . Very recently, the best known approximation factor has been improved to 0.401 [7] . On the other hand, the best hardness result is 0.478 [16, 28] .All of the algorithms improving on the 1/e ratio use oracle queries to the multilinear extension of a submodular function and its gradient. The multilinear extension relaxes the submodular set function to allow choosing an element with probability in [0, 1]. Although this is a powerful technique, the multilinear extension must be approximated by polynomially many random samples of the original set function oracle. Unfortunately, this leads to a high query complexity for these algorithms, which we term continuous algorithms; typically, the query complexity to the original submodular function is left uncomputed. As an illustration, we compute in Appendix B that the continuous algorithm of Buchbinder and Feldman [6] achieves ratio of 0.385 with query complexity of O n 11 log(n) to the set function oracle. Consequently, these algorithms are of mostly theoretical interest -the time cost of running on tiny instances (say, n < 100) is already prohibitive, as demonstrated by Chen and Kuhnle [12] where a continuous algorithm required more than 10 9 queries to the set function on an instance with n = 87, k = 10.For size and matroid constraints, the current state-of-the-art approximation ratio for a combinatorial algorithm (i.e. not continuous) is obtained by the RANDOMGREEDY algorithm (Algorithm 1) of Buchbinder et al. [9] . RANDOMGREEDY achieves ratio 1/e ≈ 0.367 for size constraint, Algorithm 1: Buchbinder et al. [9] Procedure RANDOMGREEDY (f, k):Input: oracle f , size constraint k Initialize: A 0 ← ∅ for i ← 1 to k do M i ← arg max S⊆U ,|S|=k x∈S ∆(x|A i-1 )x i ← a uniformly random element from M iA i ← A i-1 + x i end return A kand 0.283 -ε ratio for matroid constraint; its query complexity is O (kn). Thus, there is no known combinatorial algorithm that breaks the 1/e barrier; and therefore, no such algorithm is available to be used in practice on any of the applications of SM described above.Moreover, closing the gap between ratios achieved by deterministic and randomized algorithms for SM has been the focus of a number of recent works [5, 17, 11, 8] . In addition to theoretical interest, deterministic algorithms are desirable in practice, as a ratio that holds in expectation may fail on any given run with constant probability. Buchbinder and Feldman [5] introduced a linear programming method to derandomize the RANDOMGREEDY algorithm (at the expense of additional time complexity), meaning that the best known ratios for deterministic algorithms are again given by RANDOMGREEDY. There is no known method to derandomize continuous algorithms, as the only known way to approximate the multilinear extension of a general submodular set function relies on random sampling methods. Özcan et al. [26] , however, introduced a deterministic estimation via Taylor series approximation, but this approach is limited to a specific class of submodular functions that can be expressed as weighted compositions of analytic and multilinear functions. Therefore, there is no known deterministic algorithm that breaks the 1/e barrier. The best known ratio in each category of continuous, combinatorial, and deterministic algorithms is summarized in Table 1 . In this work, we consider the following questions:Can combinatorial algorithms, and separately, deterministic algorithms, obtain approximation ratios for SM beyond 1/e? If so, are the resulting algorithms practical and do they yield empirical improvements in objective value over existing algorithms?In this work, we improve the best known ratio for a combinatorial algorithm for size-constrained SM to 0.385 -ε ≈ 1/e + 0.018. This is achieved by using the result of a novel local search algorithm to guide the RANDOMGREEDY algorithm. Overall, we obtain query complexity of O (kn/ε), which is at worst quadratic in the size of the ground set, since k ≤ n. Thus, this algorithm is practical and can run on moderate instance sizes; the first algorithm with ratio beyond 1/e for which this is possible. Further, we extend this algorithm to the matroid constraint, where it improves the best known ratio of a combinatorial algorithm for a general matroid constraint from 0.283 of RANDOMGREEDY to 0.305 -ε.Secondly, we obtain these same approximation ratios with deterministic algorithms. The ideas are similar to the randomized case, except we leverage a recently formulated algorithm INTERPOLAT-EDGREEDY [11] as a replacement for guided RANDOMGREEDY. The analysis of INTERPOLATED-GREEDY has similar recurrences (up to low order terms) and the algorithm can be guided in a similar fashion to RANDOMGREEDY, but is amenable to derandomization. The derandomization only adds a constant factor, albeit one that is exponential in (1/ε).Next, we seek to lower the query complexity further, while still improving the 1/e ratio. As INTERPOLATEDGREEDY can be sped up to O ε (n log k), the bottleneck becomes the local search procedure. Thus, we develop a faster way to produce the guiding set Z by exploiting a run of (unguided) INTERPOLATEDGREEDY and demonstrating that a decent guiding set is produced if the algorithm exhibits nearly worst-case behavior. With this method, we achieve a deterministic algorithm with ratio 0.377 ≈ 1/e + 0.01 in O ε (n log k) query complexity, which is nearly linear in the size of the ground set (since k = O(n)).Finally, we demonstrate the practical utility of our combinatorial 0.385-approximation algorithm by implementing it and evaluating in the context of two applications of size-constrained SM on moderate instance sizes (up to n = 10 4 ). We evaluate it with parameters set to enforce a ratio > 1/e. It outperforms both the standard greedy algorithm and RANDOMGREEDY by a significant margin in terms of objective value; moreover, it uses about twice the queries of RANDOMGREEDY and is orders of magnitude faster than existing local search algorithms.Derandomization. Buchbinder and Feldman [5] introduced a linear programming (LP) method to derandomize the RANDOMGREEDY algorithm, thereby obtaining ratio 1/e with a deterministic algorithm. Further, Sun et al. [30] were able to apply this technique to RANDOMGREEDY for matroids. A disadvantage of this approach is an increase in the query complexity over the original randomized algorithm. Moreover, we attempted to use this method to derandomize our guided RANDOMGREEDY algorithm, but were unsuccessful. Instead, we obtained our deterministic algorithms by guiding the INTERPOLATEDGREEDY algorithm instead of RANDOMGREEDY; this algorithm is easier to derandomize, notably without increasing the asymptotic query complexity.Relationship to Buchbinder and Feldman [6] . The continuous, 0.385-approximation algorithm of Buchbinder and Feldman [6] guides the measured continuous greedy algorithm using the output of a continuous local search algorithm, in analogous fashion to how we guide RANDOMGREEDY with the output of a combinatorial local search. However, the analysis of RANDOMGREEDY is much different from that of measured continuous greedy, although the resulting approximation factor is the same.Specifically, Buchbinder and Feldman [6] obtain their ratio by optimizing a linear program mixing the continous local search and guided measured continous greedy; in contrast, we use submodularity and the output of our fast local search to formulate new recurrences for guided RANDOMGREEDY, which we then solve.Local search is a technique widely used in combinatorial optimization. Nemhauser et al. [25] introduced a local search algorithm for monotone functions under size constraint; they showed a ratio of 1/2, but noted that their algorithm may run in exponential time. Subsequently, local search has been found to be useful, especially for non-monotone functions. Chen and Kuhnle [11] proposed LINEARCARD, the first deterministic, linear-time algorithm with an 1/11.657-approximation ratio for size constraints. Also, Han et al. [17] introduced TWINGREEDY, a 0.25-approximation algorithm with a query complexity of O (kn) for matroid constraints. These algorithms are fast enough to be used as building blocks for our FASTLS, which requires as an input a constant-factor approximation in O (kn) queries.Relationship to Tukan et al. [32] . During the submission of this paper, we noticed an independent and parallel work by Tukan et al. [32] , which proposed a different 0.385-approximation algorithm.Both papers start from a similar idea-guiding the random greedy algorithm with a fast algorithm to find a local optimum. However, Tukan et al. [32] only considered size constraint and focused on algorithm speedup. They introduced a randomized local search algorithm and used its output to guide the stochastic greedy of Buchbinder et al. [9] , achieving a query complexity of O ε n + k 2 . On the other hand, we 1) address a more general constraint-matroid constraint; 2) for size constraint, present an asymptotically faster algorithm that uses a novel way of guiding with partial solutions from random greedy itself, which are not local optima, thereby achieving ratio 0.377-ε with O ε (n log(k)) queries; and 3) derandomize these algorithms.Notation. In this section, we establish the notations employed throughout the paper. We denote the marginal gain of adding A to B by ∆(A|B) = f (A ∪ B) -f (B). For every set S ⊆ U and an element x ∈ U, we denote S ∪ {x} by S + x, and S\{x} by S -x. Given a constraint and its related feasible sets I, let O ∈ arg max S∈I f (S); that is, O is an optimal solution. To simplify the pseudocode and the analysis, we add k dummy elements into the ground set, where the dummy element serves as a null element with zero marginal gain when added to any set. The symbol e 0 is utilized to represent a dummy element.Submodularity. A set function f : 2 U → R + is submodular, if ∆(x|S) ≥ ∆(x|T ) for all S ⊆ T ⊆ U and x ∈ U \ T , or equivalently, for all A, B ⊆ U, it holds that f (A) + f (B) ≥ f (A ∪ B) + f (A ∩ B).Constraints. In this paper, our focus lies on two constraints: size constraint and matroid constraint.For size constraint, we define the feasible subsets asI(k) = {S ⊆ U : |S| ≤ k},where k is an input parameter. The matroid constraint is defined in Appendix A.Organization. Our randomized algorithms are described in Section 2, with two subroutines, FASTLS and GUIDEDRG, in Section 2.1 and 2.2, respectively. Due to space constraints, we provide only a sketch of the analysis for size constraint in the main text. The full pseudocodes and formal proofs for both size and matroid constraint are provided in Appendix C. Then, we briefly sketch the deterministic approximation algorithms in Section 2.3, with full details provided in Appendix D. Next, we introduce the nearly linear-time deterministic algorithm in Section 3, with omitted analysis provided in Appendix E. Our empirical evaluation is summarized in Section 4. In Section 5, we discuss limitations and future directions.Algorithm 2: Randomized combinatorial approximation algorithm.Input: Instance (f, I), a constant-factor approximation Z 0 , switch time t ∈ [0, 1], accuracy ε > 0 Z ← FASTLS(f, I, Z 0 , ε) / * find local optimum Z * / A ← GUIDEDRG(f, I, Z, t) / * guided by local optimum Z * / return arg max{f (Z) , f (A)} 2 A Randomized (0.385 -ε)-approximation in O (kn/ε) QueriesIn this section, we present our randomized approximation algorithm (Alg. 2) for both size and matroid constraints. This algorithm improves the state-of-the-art, combinatorial approximation ratio to 0.385 -ε ≈ 1/e + 0.018 for size constraint, and to 0.305 -ε ≈ 0.283 + 0.022 for matroid constraint.Algorithm Overview. In overview, Alg. 2 consists of two components, which are detailed below. The first component is a local search algorithm, FASTLS (Alg. 4 in Appendix C.1), described in detail in Section 2.1. In brief, the local search algorithm takes an accuracy parameter ε > 0 and a constant-factor, approximate solution Z 0 as input, which may be produced by any approximation algorithm with better than O (kn) query complexity. The second component is a random greedy algorithm, GUIDEDRG (Alg. 6 in Appendix C.2), that is guided by the output Z of the local search, described in detail in Section 2.2. Also, GUIDEDRG takes a parameter t ∈ [0, 1], which is the switching time (as fraction of the budget or rank k) from guided to unguided behavior. The candidate with best f value from the two subroutines is returned.If f (Z) < αOPT (otherwise, there is nothing to show), then the local search set satisfies our definition of ((1 + ε)α, α)-guidance set (Def. 2.1 below). Under this guidance, we show that GUIDEDRG produces a superior solution compared to its unguided counterpart. The two components, FASTLS and GUIDEDRG are described in Sections 2.1 and 2.2, respectively. The following theorem is proven in Section 2.2 (size constraint) and Appendix C.2.2 (matroid constraint). Theorem 2.1. Let (f, I) be an instance of SM. Let ε > 0, and k ≥ 1/ε. Algorithm 2 achieves an expected (0.385 -ε)-approximation ratio for size constraint with t = 0.372, and an expected (0.305 -ε)-approximation ratio for matroid constraint with t = 0.559. The query complexity of the algorithm is O (kn/ε). 
the fast local search algorithm: 
 In this section, we introduce FASTLS (Alg. 4), which is the same for size or matroid constraints. There are several innovations in FASTLS that result in O (kn/ε) time complexity, where k is the maximum size of a feasible set, and ε > 0 is an input accuracy parameter.In overview, the algorithm maintains a feasible set Z; initially, Z = Z 0 , where Z 0 is an input set which is a constant approximation to OPT. The value of Z is iteratively improved via swapping, which is done in the following way. For each element a ∈ U, we compute ∆(a|Z \ a); if a ̸ ∈ Z, this is just the gain of a to Z; this requires O (n) queries. Then, if a ∈ Z and e ̸ ∈ Z such that Z \ a + e is feasible, and ∆(e|Z) -∆(a|Z \ a) ≥ ε k f (Z), then a is swapped in favor of e. If no such swap exists, the algorithm terminates.One can show that, for each swap, the value of Z increases by at least a multiplicative (1 + ε/k) factor. Since f (Z) is initialized to a constant fraction of OPT, it follows that we make at most O(k/ε) swaps. Since each swap requires O (n) queries, this yields the query complexity of the algorithm: O (kn/ε). In addition, if f is monotone, FASTLS gets ratio of nearly 1/2 for FASTLS. A second repetition of FASTLS yields a ratio of 1/4 in the case of general (non-monotone) f , as shown in Appendix C.1.2. Thus, FASTLS may be of independent interest, as local search obtains good objective values empirically and is commonly used in applications.For our purposes, we want to use the output of FASTLS to guide RANDOMGREEDY. Since we will also use another algorithm for a similar purpose in Section 3, we abstract the properties needed for such a guidance set. Intuitively, a set Z is a good guidance set if it has a low f -value and also ensures that the value of its intersection and union with an optimal solution are poor. 0 k (a) 1 e f (O) f (O) [f (O A i )] [f (A i )] 0 k (b) 1 e f (O) f (O \Z) f (O) [f (O A i )] [f ((O \Z) A i )] 0 tk k (c) 1 e f (O) f (O \Z) f (O) [f (O A i )] [f ((O \Z) A i )] [f (A i )] Figure 1: (a): The evolution of E [f (O ∪ A i )] and E [f (A i )]f (Z) < αf (O); 2) f (O ∩ Z) ≤ αf (O); 3) f (O ∪ Z) ≤ βf (O), or alternatively, 3 ′ ) f (O ∩ Z) + f (O ∪ Z) ≤ (α + β)f (O). Lemma 2.2 (proved in Appendix C.1.1) implies that for the FASTLS output Z, if f (Z) < αOPT, then Z is ((1 + ε)α, α)-guidance set.Lemma 2.2. Let ε > 0, and let (f, I(M)) be an instance of SM. The input set Z 0 is an α 0approximate solution to (f, I(M)). FASTLS (Alg. 4) returns a solution Z with O (kn log(1/α 0 )/ε)queries such that f (S ∪ Z) + f (S ∩ Z) < (2 + ε)f (Z), where S ∈ I(M).In this section, we discuss the guided RANDOMGREEDY algorithm (Alg. Overview of analysis. For clarity, we first describe the (unguided) RANDOMGREEDY analysis from Buchbinder et al. [9] . There are two recurrences: the first is the greedy gain:E [f (A i ) -f (A i-1 )] ≥ 1 k E [f (O ∪ A i-1 ) -f (A i-1 )] .Intuitively, the gain at iteration i is at least a 1/k fraction of the difference between f (O ∪ A) and A, in expectation, where A is the partial solution. If f were monotone, the right hand side would be at least (OPT -f (A))/k. However, in the case that f is not monotone, the set O ∪ A may have value smaller than OPT.To handle this case, it can be shown that the expected value of f (O ∪ A) satisfies a second recurrence:E [f (O ∪ Ai)] (a) ≥ 1 - 1 k E [f (O ∪ Ai-1)] + 1 k E [f (O ∪ Ai-1 ∪ Mi)] (b) ≥ 1 - 1 k E [f (O ∪ Ai-1)] ,where M i is the set of elements with the top k marginal gains at iteration i, (a) is from submodularity, and (b) is from nonnegativity. Thus, this expected value, while initially OPT (since A 0 = ∅), may degrade but is bounded.Both of these recurrences are solved together to prove the expected ratio of 1/e for RANDOMGREEDY: the worst-case evolution of the expected values of f (A i ), f (O ∪ A i ), according to this analysis, is illustrated in Fig. 1 (a). Observe that f (A i ) converges to OPT/e (as required for the ratio), and observe that f (O ∪ A i ) also converges to OPT/e. Thus, very little gain is obtained in the later stages of the algorithm, as illustrated in the plot. The overarching idea of the guided version of the algorithm is to obtain a better degradation of E [f (O ∪ A i )], leading to better gains later in the algorithm that improve the worst-case ratio. In the following, we elaborate on this goal, the achievement of which is illustrated in Fig. 1(c) .Stage 1: Recurrences when avoiding Z. Suppose Z is an (α, β)-guidance set, and that RANDOM-GREEDY selects elements as before, but excluding Z from the ground set. Then, the recurrences change as follows. The recurrence for the gain becomes:EQUATIONwhere O \ Z replaces O since we select elements outside of the set Z. For the second recurrence, we can lower bound the termE [f (O ∪ A i-1 ∪ M i )]using submodularity and the fact that Z ∩A i-1 = ∅:EQUATIONFinally, a similar recurrence to (2) also holds for f ((O \ Z) ∪ A i ); both are needed for the analysis. Since Z is a guidance set, by submodularity, f (O \ Z) ≥ f (O) -f (O ∩ Z) ≥ (1 -α)OPT,[f (A k )] ≥ 2 -t -1 k 1 -1 k e t-1 -e -1 -(1 + ε)α 1 -1 k 2 e t-1 -e -1 -α 1 + 1-t 1-1 k e t-1 -2 -1 k e -1 f (O) .From Lemma 2.3, we can directly prove the main result for size constraint. E [f (A k )] ≥ (2 -t -ε) (1 -ε)e t-1 -e -1 -(0.385 -0.615ε) (1 -ε) 2 e t-1 -e -1 -(0.385 -ε) 1 + 1 -t 1 -ε e t-1 -(2 -ε)e -1 f (O) (∀k ≥ 1 ε ) ≥ (0.385 -ε)f (O) . (t = 0.372)In this section, we outline the deterministic algorithms, for size and matroid constraints. The main idea is similar, but we replace GUIDEDRG with a deterministic subroutine. For simplicity, we present a randomized version in Appendix D.2 as Alg. 10, which we then derandomize (Alg. 11 in Appendix D.3). Further discussion is provided in Appendix D.Algorithm overview. Chen and Kuhnle [11] proposed a randomized algorithm, INTERPOLATED-GREEDY, which may be thought of as an interpolation between standard greedy [25] and RANDOM-GREEDY [9] . Instead of picking k elements, each randomly chosen from the top k marginal gains, it picks ℓ = O (1/ε) sets randomly from O (ℓ) candidates. Although it uses only a constant number of rounds, the recurrences for INTERPOLATEDGREEDY are similar to the RANDOMGREEDY ones discussed above, so we can guide it similarly.To select the candidate sets in each iteration, we replace INTERLACEGREEDY (the subroutine of INTERPOLATEDGREEDY proposed in Chen and Kuhnle [11] ) with a guided version: GUIDEDIG-S (Alg. 9 in Appendix D. 3 Deterministic Algorithm with Nearly Linear Query ComplexityIn this section, we sketch a deterministic algorithm with (0.377 -ε) approximation ratio and O ε (n log(k)) query complexity for the size constraint. A full pseudocode (Alg. 14) and analysis is provided in Appendix E.Description of algorithm. Our goal is to improve the asymptotic O ε (kn) query complexity. Recall that in Section 2, we described a deterministic algorithm that employed the output of local search to guide the INTERPOLATEDGREEDY algorithm, which obeys similar recurrences to RAN-DOMGREEDY. To produce the ℓ candidate sets for each iteration of INTERPOLATEDGREEDY, a greedy algorithm (guided INTERLACEGREEDY) is used. These algorithms can be sped up using a descending thresholds technique. This results in THRESHGUIDEDIG (Alg. 12 in Appendix E.1), which achieves O ε (n log k) query complexity for the guided part of our algorithm. However, the local search FASTLS still requires O (kn/ε) queries, so we seek to find a guidance set in a faster way.Recall that, in the definition of guidance set Z, the value f (Z) needs to dominate both f (O ∩ Z) and f (O ∪ Z). To achieve this with faster query complexity, we employ a run of unguided INTERPOLATEDGREEDY. Consider the recurrences plotted in Fig. 1 (a) -if the worst-case degradation occurs, then at some point the value of f(A i ) becomes close to f (O ∪ A i ).On the other hand, if the worst-case degradation does not occur, then the approximation factor of INTERPOLATEDGREEDY is improved (see Fig. 2 ). Moreover, if we ensure that at every stage, A i contains no elements that contribute a negative gain, then we will also have f(A i ) ≥ f (O ∩ A i ).To execute this idea, we run (derandomized, unguided) INTERPOLATEDGREEDY, and consider all O ℓ ℓ intermediate solutions. Each one of these is pruned (by which we mean, any element with negative contribution is discarded until none such remain). Then, the guided part of our algorithm executes with every possible candidate intermediate solution as the guiding set; finally, the feasible set encountered with maximum f value is returned. Figure 3 : The objective value (higher is better) and the number of queries (log scale, lower is better) are normalized by those of STANDARDGREEDY. Our algorithm (blue star) outperforms every baseline on at least one of these two metrics.The tradeoff between the first and second parts of the algorithm is optimized with α = 0.377 and β = 0.46. That is, if INTERPOLATEDGREEDY produces an (α, β)-guidance set, the guided part of our algorithm achieves ratio 0.377; otherwise, INTERPOLATEDGREEDY has ratio at least 0.377. We have the following theorem. The algorithms and analysis sketched here are formalized in Appendix E.Theorem 3.1. Let (f, k) be an instance of SM, with the optimal solution set O. Algorithm 14 achieves a deterministic (0.377 -ε) approximation ratio with O(n log(k)ℓ 1 2ℓ1 ℓ 2 2ℓ2-1 ) queries, where ℓ 1 = 10 3ε and ℓ 2 = 5 ε .By Lemma D.1 in Appendix D.1 and the closed form for a recurrence provided in Lemma A.3, the following corollary holds, Corollary D.2. After iteration i of the for loop in Alg. 10, the following inequalities hold,E [f (A i )] ≥ 1 - 2 ℓ E [f (A i-1 )] + 1 ℓ + 1 1 - 1 ℓ f (O \ Z) - 1 2 1 -1 - 2 ℓ i-1 f (O ∪ Z) , 1 ≤ i ≤ tℓ E [f (A i )] ≥ 1 - 2 ℓ E [f (A i-1 )] + 1 ℓ + 1 1 - 1 ℓ 1 2 1 + 1 - 2 ℓ i-tℓ f (O) - 1 2 1 - 2 ℓ i-tℓ -1 - 2 ℓ i f (O ∪ Z) , tℓ < i ≤ ℓ Proof of approximation ratio. If f (Z) ≥ (0.305 -ε)f (O), the approximation ratio holds immediately. So, we analyze the case f (Z) < (0.305 -ε)f (O) in the following.Recall that Z is a (1 + ε)α, α)-guidance set in Corollary C.1, it holds that f (O ∪ Z) + f (O ∩ Z) < (0.61 -1.695ε)f (O) and f (O ∩ Z) < (0.305 -0.695ε)f (O).By repeatedly implementing Lemma A.3 with the recursion in Corollary D.2, it holds thatEQUATIONE [f (A ℓ )] ≥ 1 - 2 ℓ ℓ-⌊tℓ⌋ E f A ⌊tℓ⌋ + ℓ -1 2(ℓ + 1) 1 2 + 1 2 -t + 1 ℓ 1 - 2 ℓ ℓ-⌊tℓ⌋-1 f (O) -(1 -t) 1 - 2 ℓ ℓ-⌊tℓ⌋-1 -1 - 2 ℓ ℓ-1 f (O ∪ Z) ≥ ℓ -1 2(ℓ + 1) 1 2 + 3 2 -t - 1 ℓ 1 - 2 ℓ ℓ-tℓ -1 - 2 ℓ ℓ f (O) - 1 - 2 ℓ (1-t)ℓ -1 - 2 ℓ ℓ f (O ∩ Z) - 1 2 + 1 -t 1 -2 ℓ 1 - 2 ℓ ℓ-tℓ - 3 2 - 1 ℓ 1 - 2 ℓ ℓ-1 f (O ∪ Z) (tℓ -1 < ⌊tℓ⌋ ≤ tℓ) ≥ ℓ -1 2(ℓ + 1) 1 2 + 3 2 -t - 1 ℓ 1 - 2 ℓ e 2(t-1) -e -2 f (O) -e 2(t-1) -1 - 2 ℓ e -2 f (O ∩ Z) - 1 2 + 1 -t 1 -2 ℓ e 2(t-1) - 3 2 - 1 ℓ e -2 f (O ∪ Z) (Lemma A.4; nonnegativity) ≥ ℓ -1 2(ℓ + 1) 1 2 + 3 2 -t - 1 ℓ 1 - 2 ℓ e 2(t-1) -e -2 f (O) - 1 2 + 1 ℓ e -2 - 1 2 -t e 2(t-1) f (O ∩ Z) - 1 2 + 1 -t 1 -2 ℓ e 2(t-1) - 3 2 - 1 ℓ e -2 (f (O ∪ Z) + f (O ∩ Z)) ≥ ℓ -1 2(ℓ + 1) 1 2 + 3 2 -t - 1 ℓ 1 - 2 ℓ e 2(t-1) -e -2 -(0.305 -0.695ε) 1 2 + 1 ℓ e -2 - 1 2 -t e 2(t-1) -(0.61 -1.695ε) 1 2 + 1 -t 1 -2 ℓ e 2(t-1) - 3 2 - 1 ℓ e -2 f (O) ≥ (0.305 -ε)f (O) (ℓ = 10 9ε ; 0 < ε < 0.305; t = 0.559) D.3 Derandomize Alg. 10 in Section 2.3In this section, we present the deranmized version of Alg. 10, which simply evaluates all possible paths and returns the best solution. We reiterate the guarantee as follows.Theorem 2.4. Let (f, k) be an instance of SM, with the optimal solution set O. Alg. 11 achieves a deterministic (0.385 -ε) approximation ratio with t = 0.372, and a deterministic (0.305 -ε) approximation ratio with t = 0.559. The query complexity of the algorithm is O knℓ 2ℓ-1 where ℓ = 10 9ε .In this section, we provide the pseudocode and additional analysis of our nearly linear time deterministic algorithm introduced in Section 3. We organize this section as follows: in Appendix E.1, weif i ≤ tℓ then 20 G i ← G i ∪ GUIDEDIG-M(f, k, Z, A i-1 , ℓ) 21 else 22 G i ← G i ∪ GUIDEDIG-M(f, k, ∅, A i-1 , ℓ) 23 end end end end return A * ← arg max{f (Z) , f (A ℓ ) : A ℓ ∈ G ℓ }provide a speedup version of GUIDEDIG-S which queries O (n log(k)) times; in Appendix E.2, we analyze the subroutine, PRUNE; at last, in Appendix E.3, we provide the pseudocode of nearly linear time deterministic algorithm and its analysis.In this section, we provide the algorithm THRESHGUIDEDIG, which combines the guiding and descending threshold greedy techniques with INTERLACEGREEDY [11] . Lemma E.1. Let O ⊆ U be any set of size at most k, and suppose THRESHGUIDEDIG(Alg. 12) is called with (f, k, Z, G, ℓ). Then THRESHGUIDEDIG outputs ℓ(ℓ + 1) candidate sets with O ℓ 2 n log(k)/ε queries. Moreover, with a probability of (ℓ + 1) -1 , a randomly selected set A from the output satisfies that:1) ℓ 1 -ε + 1 E [f (A)] ≥ E [f ((O \ Z) ∪ A)] + ℓ 1 -ε f (G) -εf (O); 2) E [f (O ∪ A)] ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ (f (O ∪ (Z ∩ G)) -f (O ∪ Z)) 3) E [f ((O \ Z) ∪ A)] ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ (f ((O \ Z) ∪ (Z ∩ G)) -f (O ∪ Z)).Proof. Let o max = arg max o∈O\(G∪Z) ∆(o|G), and let {a 1 , . . . , a ℓ } be the largest ℓ elements of {∆(x|G) : x ∈ U \ (G ∪ Z)}, as chosen on Line 13. We consider the following two cases. For any l ∈ [ℓ], let A (j) 0,l be A 0,l after we add j elements into it, τ (j) l be τ l when we adopt j-th elements into A 0,l , and τ (1) 0,l , the next ℓ elements are not selected in any set before we get AA u,l ← G ∪ {a u }, for any l ∈ [ℓ] end τ l ← M , I l ← true, for any l ∈ [ℓ] while ∨ ℓ l=1 I l do for i ← 1 to ℓ do if I i then V ← U \ ∪ ℓ l=1 A u,l ∪ Z A u,i , τ i ← ADD(f, V, A u,i , ε, τ i , εM k ) if |A u,i \ G| = k/ℓ ∨ τ i < εM k then I i ← false end end end G m ← G m ∪ {A u,1 , A u,2 , . . . , A u,ℓ } end return S * ← arg max{f (S ℓ ) : S ℓ ∈ G ℓ } 25 Procedure ADD (f, V, A, ε, τ, τ(2) 0,l , and so on. Therefore, for any j ≤ |A 0,l \ G| and ℓ(j -1) + 1 ≤ i ≤ ℓj, o i are filtered out by A 0,l with threshold τ(j) l /(1 -ε), which follows that ∆ o i |A (j) 0,l < τ (j) l /(1-ε) ≤ (f (A (j) 0,l )-f (A (j-1) 0,l))/(1-ε); for any ℓ|A 0,l \G| < i ≤ |O\(G∪Z)|, o i are filtered out by A 0,l with threshold εM k , which follows that ∆(o i |A 0,l ) < εM/k. Thus,f ((O \ Z) ∪ A 0,l ) -f (A 0,l ) ≤ o∈O\A 0,l ∆(o|A 0,l ) (submodularity) ≤ o∈O\(G∪Z) ∆(o|A 0,l ) (G ⊆ A 0,l ) ≤ ℓ i=1 ∆ o i |A (1) 0,l + 2ℓ i=ℓ+1 ∆ o i |A (2) 0,l + . . . + i>ℓ|A 0,l \G| ∆(o i |A 0,l ) (submodularity) ≤ ℓ • f (A 0,l ) -f (G) 1 -ε + εM ≤ ℓ • f (A 0,l ) -f (G) 1 -ε + εf (O) .By summing up the above inequality with all 1 ≤ l ≤ ℓ, it holds thatEQUATION) Since A u,l1 ∩ A u,l2 = G for any 1 ≤ l 1 ̸ = l 2 ≤ ℓ it holds that ((O \ Z) ∪ A u,l1 ) ∩ ((O \ Z) ∪ A u,l2 ) = (O \ Z) ∪ G.By repeated application of submodularity, it holds thatE [f ((O \ Z) ∪ A)] = 1 ℓ ℓ i=1 f ((O \ Z) ∪ A 0,i ) ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ f (O \ Z) ∪ ∪ ℓ i=1 A 0,i ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ (f ((O \ Z) ∪ (Z ∩ G)) -f (O ∪ Z)) E [f (O ∪ A)] = 1 ℓ ℓ i=1 f (O ∪ A 0,i ) ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ f O ∪ ∪ ℓ i=1 A 0,i ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ (f (O ∪ (Z ∩ G)) -f (O ∪ Z)) .Therefore, the last two inequalities in the theorem hold.Case (O \ (G ∪ Z)) ∩ {a 1 , . . . , a ℓ } ̸ = ∅. Then o max ∈ {a 1 , . . . , a ℓ }. Suppose that a u = o max . We analyze that lemma holds with sets {A u,l } ℓ l=1 .Similar to the analysis of the previous case, let A (j) 0,l be A 0,l after we add j elements into it, τ (j) l be τ l when we adopt j-th elements into A 0,l , and τ(1) l = M . By Line 10, it holds that Au,l = G ∪ {a u }. Then, we can order O \ (G ∪ Z ∪ {a u }) = {o 1 , o 2 , . . .} such that the first ℓ elements are not selected by any set before we get A (1) u,l , the next ℓ elements are not selected in any set before we get A(2) u,l , and so on. Therefore, Inequality 8 also holds in this case, where A is a random set from {A u,l } ℓ l=1 . Since, a u ∈ O, andA u,l1 ∩ A u,l2 = G ∪ {a u } for any 1 ≤ l 1 ̸ = l 2 ≤ ℓ, it holds that ((O \ Z) ∪ A u,i1 ) ∩ ((O \ Z) ∪ A u,i2 ) = O ∪ G. Following the proof of case (O \ (G ∪ Z)) ∩ {a 1 , .. . , a ℓ } = ∅, the last two inequalities still hold in this case.Overall, since either one of the above cases happens, the theorem holds.PRUNE is used in Alg. 14 to help construct the (α, β)-guidance set, where α = 0.377 and β = 0.46. In this section, we provide the pseudocode, guarantee and its analysis. Lemma E.2. Suppose PRUNE(Alg. 13) is called with (f, A) and returns the set A ′ . For every A ∈ A and its related output set A ′ ∈ A ′ , it holds that,1) f (A ′ ) ≥ f (A) ; 2) f (S ∪ A ′ ) ≥ f (S ∪ A) , ∀S ⊆ U; 3) f (T ) ≤ f (A ′ ) , ∀T ⊆ A ′ .Algorithm 13: A pruning algorithm which deletes element with negative marginal gain Procedure PRUNE (f, A):Input: oracle f , a sequence of subsets A Initialize: A ′ ← ∅ for A ∈ A do for x ∈ A do 6 if ∆(x|A -x) < 0 then A ← A -x end A ′ ← A ′ ∪ {A} end return A ′Proof. Let A i be A after we delete i-th element x i , A 0 be the input set A, A m be the output set A ′ . Since any element x i being deleted follows that ∆(x i |A i ) < 0, it holds that f (A i ) > f (A i + x i ) = f (A i-1 ). Therefore, f (A ′ ) = f (A m ) > . . . > f (A 0 ) = f (A).The first inequality holds.i ∈ A \ A ′ , it holds that ∆(x i |A i ) < 0. By submodularity, f (S ∪ A) -f (S ∪ A ′ ) = m i=1 ∆(x i |S ∪ A i ) ≤ m i=1 ∆(x i |A i ) < 0.The second inequality holds.For any y ∈ A ′ \ T , since it is not deleted, there exists 0 ≤ i y ≤ m such that ∆ y|A iy ≥ 0. By submodularity,f (A ′ ) -f (T ) ≥ y∈A ′ \T ∆(y|A ′ ) ≥ y∈A ′ \T ∆ y|A iy ≥ 0.The third inequality holds. Then PRUNE(THRESHGUIDEDIG(f, k, ∅, G, ℓ)) outputs ℓ(ℓ + 1) candidate sets with O ℓ 2 n log(k)/ε queries. Moreover, with a probability of (ℓ + 1) -1 , a randomly selected set A from the output satisfies that:1) ℓ 1 -ε + 1 E [f (A)] ≥ 1 - 1 ℓ f (O ∪ G) + ℓ 1 -ε f (G) -εf (O); 2) E [f (O ∪ A)] ≥ 1 - 1 ℓ f (O ∪ G); 3) f (O ∩ A) ≤ f (A).Theorem 3.1. Let (f, k) be an instance of SM, with the optimal solution set O. Algorithm 14 achieves a deterministic (0.377 -ε) approximation ratio with O(n log(k)ℓ 1 2ℓ1 ℓ 2 2ℓ2-1 ) queries, where ℓ 1 = 10 3ε and ℓ 2 = 5 ε .Proof. Following the proof of Theorem 3.1, we consider two cases of the algorithm.Case 1. For every A ∈ Z, it holds that f (O∪A) ≥ 0.46f (O). Then, we prove that max C∈Z f (C) ≥ (0.377 -ε)f (O).In the following, we prove the theorem by analyzing the random case of the algorithm, where we randomly select a set from the output of PRUNE (THRESHGUIDEDIG). Suppose that we successfullly select a set where the inequalities in Corollary E.1 hold. Let A i and A i-1 be random sets in Z i Algorithm 14: Nearly linear-time deterministic algorithm for size constraintInput: oracle f , size constraint k, error rate ε Initialize ε ′ = 2 ε , ℓ 1 ← 5 3ε ′ , ℓ 2 ← 5 2ε ′ , t ← 0.3 ▷ Create guided sets Z 0 ← ∅ for i ← 1 to ℓ 1 do Z i ← ∅ for A i-1 ∈ Z i-1 do Z i ← Z i ∪ PRUNE(THRESHGUIDEDIG(f, k, ∅, A i-1 , ℓ 1 , ε ′ )) end end Z ← ∪ ℓ1 i=1 Z i ▷ Build solution based on guided sets G ← ∅ for A ∈ Z do G 0 ← ∅ for i ← 1 to ℓ 2 do G i ← ∅ for B i-1 ∈ G i-1 do 19 if i ≤ tℓ then 20 G i ← G i ∪ THRESHGUIDEDIG(f, k, A, B i-1 , ℓ 2 , ε ′ ) 21 else 22 G i ← G i ∪ THRESHGUIDEDIG(f, k, ∅, B i-1 , ℓ 2 , ε ′ ) 23 end end end G ← G ∪ G ℓ2 end return C * ← arg max C∈Z∪G f (C) and Z i-1 , respectively. Let 1 -1 ℓ1 i * -1 > 0.46 ≥ 1 -1 ℓ1 i *. Then, by Inequality (2) inCorollary E.1, when i < i * , E [f (O ∪ A i )] ≥ 1 -1 ℓ1 i f (O); when i ≥ i * , f (O ∪ A i ) ≥ 0.46f (O)by assumption. By applying Inequality (1) in Corollary E.1,E [f (A i * )] ≥   i * ℓ1 1-ε ′ + 1 1 - 1 ℓ 1 i * -ε ′   1 -1 - 1 ℓ1 1-ε ′ + 1 i *     f (O) E [f (A ℓ1 )] ≥ 1 - 1 ℓ1 1-ε ′ + 1 ℓ1-i * E [f (A i * )] +   1 -1 - 1 ℓ1 1-ε ′ + 1 ℓ1-i *   (0.46 -ε ′ )f (O) ≥   i * ℓ1 1-ε ′ + 1 1 - 1 ℓ 1 i * 1 - 1 ℓ1 1-ε ′ + 1 ℓ1-i * +   1 -1 - 1 ℓ1 1-ε ′ + 1 ℓ1-i *   0.46 -ε ′   1 -1 - 1 ℓ1 1-ε ′ + 1 ℓ1     f (O) ≥     log(0.46) ℓ1 1-ε ′ + 1 log 1 -1 ℓ1 1 - 1 ℓ 1 e -1 +     1 - e ε ′ -1 0.46 1 - 1 ℓ 1 1-ε ′ +1     0.46 -ε ′ 1 -e -1+ε ′     f (O) (Lemma A.4; 1 -1 ℓ1 i * -1 > 0.46 ≥ 1 -1 ℓ1 i * ) ≥ (0.377 -ε)f (O) (ℓ 1 = 5 3ε ′ ; ε ′ = ε 2 ; 0 < ε < 0.377) Since we return the best solution in Z and G, it holds that f (C * ) ≥ E [f (A ℓ1 )] ≥ (0.377 -ε)f (O).Case 2. There exists A ∈ Z, such that f (O∪A) < 0.46f (O). Then, we prove that max C∈G f (C) ≥ (0.377 -ε)f (O).Suppose that f (A) < 0.377f (O). Otherwise, f (C * ) ≥ 0.377f (O) immediately. By Inequality (3) in Corollary E.2, it holds that f (O ∩ A) ≤ f (A) < 0.377f (O). Let B ℓ2 be a randomly selected set in G ℓ2 , where we calculate G ℓ2 with the guidance set A and inequalities in Theorem D.2 hold successfully. In the following, we also consider that randomized version of the algorithm, where we randomly select a set B i from all the solution set returned by THRESHGUIDEDIG. Suppose that we successfully select a set where the inequalities in Lemma E.1 hold. Then, the recursion of E [f (B i )] can be calculated as follows,E [f (B i )] ≥ ℓ2 1-ε ′ ℓ2 1-ε ′ + 1 E [f (B i-1 )] + 1 ℓ2 1-ε ′ + 1 f (O \ A) -1 -1 - 1 ℓ 2 i f (O ∪ A) -ε ′ f (O) , 1 ≤ i ≤ tℓ 2 E [f (B i )] ≥ ℓ2 1-ε ′ ℓ2 1-ε ′ + 1 E [f (B i-1 )] + 1 ℓ2 1-ε ′ + 1 1 - 1 ℓ 2 i-⌊tℓ2⌋ -ε ′ f (O) - 1 - 1 ℓ 2 i-⌊tℓ2⌋ -1 - 1 ℓ 2 i f (O ∪ A) , tℓ 2 < i ≤ ℓ 2Then, by solving the above recursion, it holds thatE f B ⌊tℓ2⌋ ≥ 1 -1 - 1 ℓ 2 ⌊tℓ2⌋ (f (O \ A) -f (O ∪ A) -ε ′ f (O)) + ⌊tℓ 2 ⌋ ℓ2 1-ε ′ + 1 1 - 1 ℓ 2 ⌊tℓ2⌋ f (O ∪ A) E [f (B ℓ2 )] ≥ 1 - 1 ℓ 2 ℓ2⌊tℓ2⌋ E f B ⌊tℓ2⌋ + ℓ 2 ⌊tℓ 2 ⌋ ℓ2 1-ε ′ + 1 1 - 1 ℓ 2 ℓ2⌊tℓ2⌋ f (O) -1 -1 - 1 ℓ 2 ⌊tℓ2⌋ f (O ∪ A) - ε ′ ℓ 2 ℓ2 1-ε ′ + 1 1 -1 - 1 ℓ 2 ℓ2⌊tℓ2⌋ f (O) ≥ 1 - 1 ℓ 2 (1-t)ℓ2+1 -1 - 1 ℓ 2 ℓ2 (f (O) -f (O ∩ A) -f (O ∪ A) -ε ′ f (O)) + (1 -t)ℓ 2 ℓ2 1-ε ′ + 1 1 - 1 ℓ 2 (1-t)ℓ2+1 f (O) - ℓ 2 ℓ2 1-ε ′ + 1 (1 -t) 1 - 1 ℓ 2 (1-t)ℓ2 -1 - 1 ℓ 2 ℓ2 f (O ∪ A) - ε ′ ℓ 2 ℓ2 1-ε ′ + 1 1 -1 - 1 ℓ 2 (1-t)ℓ2+1 f (O) (tℓ 2 -1 < ⌊tℓ 2 ⌋ ≤ tℓ 2 ) ≥ 1 - 1 ℓ 2 2 e t-1 -e -1 (f (O) -f (O ∩ A) -f (O ∪ A) -ε ′ f (O)) + (1 -t)(ℓ 2 -1) ℓ2 1-ε ′ + 1 1 - 1 ℓ 2 e t-1 f (O) - ℓ 2 ℓ2 1-ε ′ + 1 (1 -t)e t-1 -1 - 1 ℓ 2 e -1 f (O ∪ A) - ε ′ ℓ 2 ℓ2 1-ε ′ + 1 1 -1 - 1 ℓ 2 2 e t-1 f (O) (f (O ∩ A) + f (O ∪ A) ≥ 0.837f (O); Lemma A.4) ≥ (1 -t)(ℓ 2 -1) ℓ2 1-ε ′ + 1 + 1 - 1 ℓ 2 1 - 1 ℓ 2 e t-1 -e -1 -ε ′ 1 -e -1 f (O) -e t-1 -e -1 f (O ∩ A) -(2 -t)e t-1 -2 - 1 ℓ 2 e -1 f (O ∪ A) ≥ (1 -t)(ℓ 2 -1) ℓ2 1-ε ′ + 1 + 1 - 1 ℓ 2 1 - 1 ℓ 2 e t-1 -e -1 -ε ′ 1 -e -1 -0.377 e t-1 -e -1 -0.46 (2 -t)e t-1 -2 - 1 ℓ 2 e -1 f (O) (f (O ∩ A) < 0.377f (O); f (O ∪ A) < 0.46f (O)) ≥ (0.377 -ε)f (O) (t = 0.3; ℓ 2 = 5 2ε ′ ; ε ′ = ε 2 )Experimental setup We run all experiments on an Intel Xeon(R) W5-2445 CPU at 3.10 GHz with 20 cores, 64 GB of memory, and one NVIDIA RTX A4000 with 16 GB of memory. For Maximum Cut experiments, we use the standard multiprocessing provided in Python, which takes about 20 minutes to complete, while the video summarization finishes in under a minute.In this section, you can find the tables and plots omitted in the main paper due to space constraints. In Figure 5 , we compare the frames selected by FASTLS +RANDOMGREEDY and STANDARDGREEDY, and in Figure 6 , we report the results for Barab'asi-Albert and Watts-Strogatz models for Maximum Cut.In this section, we formally introduce video summarization and Maximum Cut.Formally, given n frames from a video, we present each frame by a p-dimensional vector. Let X ∈ R n×n be the Gramian matrix of the n resulting vectors so X ij quantifies the similarity between two vectors through their inner product. The Determinantal Point Process (DPP) objective function is defined by the determinant function f : 2 n → R : f (S) = log(det(X S ) + 1), where X S is the principal submatrix of X indexed by S following Banihashem et al. [1] to make the objective function f a non-monotone non-negative submodular function. For all experiments, we set the error rate, ϵ, to 0.01 for FASTLS +GUIDEDRG and to 0.1 for Lee et al. [21] . Additionally, for video summarization, we run RANDOMGREEDY 20 times and report the standard deviation of these runs. For all other experiments, we run the algorithms once per instance and report the standard deviation over instances. Queries / Greedy (d) Watts Strogatz, queries Figure 6 : The objective value (higher is better) and the number of queries (lower is better) are normalized by those of STANDARDGREEDY. Our algorithm (blue star) outperforms every baseline on at least one of these two metrics.The video we select [29] (available under CC BY license) for video summarization lasts for roughly 4 minutes, and we uniformly sample 100 frames from the video to form the ground set. For maximum cut, we run experiments on synthetic random graphs, each distribution consisting of 20 graphs of size 10, 000 vertices generated using the Erdős-Renyi (ER), Barabasi-Albert (BA), and Watts-Strogatz (WS) models. The ER graphs are generated with p = 0.001, while the WS graphs are created with p = 0.001 and 10 edges per node. For the BA model, graphs are generated by adding m = 2 edges in each iteration. Data and code are provided in the supplementary material to regenerate the empirical results provided in the paper.For our implementation of FASTLS, we take the solution of STANDARDGREEDY as our initial solution Z 0 ; the theoretical guarantee is thus f (Z 0 ) > OPT/k, since Z 0 has higher f -value than the maximum singleton. This increases the theoretical query complexity of our algorithm as implemented to O kn ε log( k ε ) . Then, for each swap, we find the best candidates to remove from and add to the current solution set (including the dummy element), rather than any pair that satifies the criterion. For guided GUIDEDRG, we implement exactly as in the pseudocode (Alg. 6) -we remark that we could instead use (a guided version of) the linear-time variant of RANDOMGREEDY [10] to reduce the empirical number of queries further, but for simplicity we did not do this in our evaluation.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: Our experiments are not large-scale, and modern desktop hardware should be sufficient to reproduce all results in a few hours.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
empirical evaluation: 
 In this section, along with Appendix F, we implement and empirically evaluate our randomized (0.385 -ε)-approximation algorithm (Alg. 2, FASTLS+GUIDEDRG) on two applications of sizeconstrained SM, and compare to several baselines in terms of objective value of solution and number of queries to f . In summary, our algorithm uses roughly twice the queries as the standard greedy algorithm, but obtains competitive objective values with an expensive local search that uses one to two orders of magnitude more queries. 1 Baselines. 1) STANDARDGREEDY: the classical greedy algorithm [25] , which often performs well empirically on non-monotone objectives despite having no theoretical guarantee. 2) RANDOM-GREEDY, the current state-of-the-art combinatorial algorithm as discussed extensively above.3)The local search algorithm of Lee et al. [21] , which is the only prior polynomial-time local search algorithm with a theoretical guarantee: ratio 1/4 -ε in O k 5 log(k)n/ε queries. As our emphasis is on theoretical guarantees above 1/e, we set ε = 0.01 for our algorithm, which yields ratio at least 0.375 in this evaluation. For Lee et al. [21] , we set ε = 0.1, which is the standard value of the accuracy parameter in the literature -running their algorithm with ε = 0.01 produced identical results.Applications and datasets. For instances of SM upon which to evaluate, we chose video summarization and maximum cut (MC). For video summarization, our objective is to select a subset of frames from a video to create a summary. As in Banihashem et al. [1] , we use a Determinantal Point Process objective function to select a diverse set of elements [20] . Maximum cut is a classical example of a non-monotone, submodular objective function. We run experiments on unweighted Erdős-Rényi (ER), Barabási-Albert (BA) and Watts-Strogatz (WS) graphs which have been used to model many real-world networks. The formal definition of problems, details of datasets, and hyperparameters of graph generation can be found in the Appendix F. In video summarization, there are n = 100 frames. On all the instances of maximum cut, the number of vertices n = 10000. The mean of 20 independent runs is plotted, and the shaded region represents one standard deviation about the mean.Results. As shown in Figure 3 in this section, and Figure 5 and 6 in Appendix F, on both applications, FASTLS +GUIDEDRG produces solutions of higher objective value than STANDARDGREEDY, and also higher than RANDOMGREEDY. The objective values of FASTLS +GUIDEDRG often matches with Lee et al. [21] which performs the best; this agrees with the intuition that, empirically, local search is nearly optimal. In terms of queries, our algorithm uses roughly twice the number of queries as STANDARDGREEDY, but we improve on Lee et al. [21] typically by at least a factor of 10 and often by more than a factor of 100. 
discussion and limitations: 
 Prior to this work, the state-of-the-art combinatorial ratios were 1/e ≈ 0.367 and 0.283 for size constrained and matroid constrained SM, respectively, both achieved by the RANDOMGREEDY algorithm. In this work, we show how to guide RANDOMGREEDY with a fast local search algorithm to achieve ratios 0.385 and 0.305, respectively, in O (kn/ε) queries. The resulting algorithm is practical and empirically outperforms both RANDOMGREEDY and standard greedy in objective value on several applications of SM. However, if k is on the order of n, the query complexity is quadratic in n, which is too slow for modern data sizes. Therefore, an interesting question for future work is whether further improvements in the query complexity to achieve these ratios (or better ones) could be made.In addition, we achieve the same approximation ratios and asymptotic query complexity with deterministic algorithms, achieved by guiding a different algorithm; moreover, we speed up the deterministic algorithm to O ε (n log k) by obtaining the guidance set in another way. This result is a partial answer to the limitation in the previous paragraph, as we achieve a ratio beyond 1/e in nearly linear query complexity. However, for all of our deterministic algorithms, there is an exponential dependence on 1/ε, which makes these algorithms impractical and mostly of theoretical interest.In this paper, our focus lies on two constraints: size constraint and matroid constraint. For size constraint, we define the feasible subsets as I(k) = {S ⊆ U : |S| ≤ k}. For matroid constraint, the definition is as follows:Definition A.1. A matroid M is a pair (U, I), where U is the ground set and I is the independent sets with the following properties: (1) ∅ ∈ I; (2) hereditary property:A ∈ I ⇒ B ∈ I, ∀B ⊆ A; (3) exchange property: A, B ∈ I, |A| > |B| ⇒ ∃x ∈ A \ B, s.t.B + x ∈ I.Specifically, we use I(M) to represent the independent sets of matroid M. A maximal independent set in I(M) is called a basis. Let k be the size of the maximal independent set.In the following, we consider an extended matroid with k dummy elements added to the ground set M ′ = (U ′ , I ′ ). We show that SM on M ′ return the same solution as on M.Lemma A.1. Let M = (U, I) be a matroid, andU ′ = U ∪ E, where E = {e 1 0 , . . . , e k 0 } and e i 0 is a dummy element for each i ∈ [k]. Let I ′ = S∈I {S, S ∪ {e 1 0 }, . . . , S ∪ {e 1 0 , . . . , e k-|S| 0 }}. Then, M ′ = (U ′ , I ′ ) is also a matroid and max S∈I f (S) = max S∈I ′ f (S).Proof. Firstly, we prove that M ′ = (U ′ , I ′ ) is also a matroid by Definiton A.1.I ⊆ I ′ , it holds that ∅ ∈ I ′ . Let A ′ ∈ I ′ , and A = A ′ \ E. Then, A ∈ I. For every B ′ ⊆ A ′ , since (U, I) is a matroid, B = B ′ \ E ⊆ A ∈ I. Since |B ′ ∩ E| ≤ |A ′ ∩ E| ≤ k -|A| ≤ k -|B|, it holds that B ∈ I ′ by the construction of I ′ . Let A ′ , B ′ ∈ I ′ and |A ′ | > |B ′ |. Let A = A ′ \ E and B = B ′ \ E. Then, A, B ∈ I. If |A| > |B|, by Def. A.1, there exists x ∈ A \ B s.t. B + x ∈ I. Since (B ′ + x) \ (B + x) ⊆ E and |B ′ | < |A ′ | ≤ k, B ′ + x ∈ I ′ . Otherwise, |A| < |B|, which indicates that |A ′ ∩ E| > |B ′ ∩ E|. Since |B ′ | < |A ′ | ≤ k, by adding a dummy element e 0 ∈ A ′ ∩ E \ B ′ to B ′ , it holds that B ′ + e 0 ∈ I ′ .Thus, by Def. A.1, M ′ = (U ′ , I ′ ) is also a matroid.As for SM on I ′ , since dummy element does not contribute to the objective value, it holds that, for every S ∈ I, f (S) = f (S ∪ E ′ ), where E ′ ⊆ E. Then, {f (S) : S ∈ I} = {f (S) : S ∈ I ′ }. Further, max S∈I f (S) = max S∈I ′ f (S).Lemma A.2. (Brualdi [4] ) If B 1 and B 2 are finite bases, then there exists a bijection σ :B 1 \ B 2 → B 2 \ B 1 such that B 2 + e -σ(e) is a basis for all e ∈ B 1 \ B 2 Lemma A.3. Let a ∈ R + , b, X 0 ∈ R. If X i ≥ aX i-1 + b for every i ∈ [k], then X k ≥ a k X 0 + b 1 -a k 1 -a .Proof. By repeatedly implementing that X i ≥ aX i-1 + b, we can bound X k as follows,X k ≥ aX k-1 + b ≥ a 2 X k-2 + ab + b . . . ≥ a k X 0 + b k-1 i=0 a i = a k X 0 + b 1 -a k 1 -a . Lemma A.4. 1 - 1 x ≤ log(x) ≤ x -1, ∀x > 0 1 - 1 x + 1 ≥ e -1 x , ∀x ∈ R (1 -x) y-1 ≥ e -xy , ∀xy ≤ 1B Query Complexity Analysis of the Continuous Algorithm in Buchbinder and Feldman [6] Algorithm 3: Aided Measured Continuous Greedy (f, P, Z, t s ) [6] input :oracle f , a solvable down-closed polytope P , a set Z ∈ U, t s ∈ (0, 1)/ * Initialization * / Let δ1 ← t s • n -4 and δ2 ← (1 -t s ) • n -4 Let t ← 0 and y(t) ← 1 ∅ / * Growing y(t) * / while t < 1 do foreach u ∈ U do Let w u (t) be an estimate of E [∆(u|R(y(t)))] obtained by averaging the values of ∆(u|R(y(t))) for r = 48n 6 log(2n) independent samples of R(y(t)) end Let x(t) ← arg max x∈P u∈U \Z w u (t) • x u (t) -u∈Z x u (t) if t ∈ [0, t s ) , arg max x∈P u∈U w u (t) • x u (t) if t ∈ [t s , 1) .Let δ t be δ1 when t < t s and δ2 when t ≥ t s Let y (t + δ t ) ← y(t)+ δ t (1 U -y(t)) • x(t) Update t ← t + δ t end return y(1)In this section, we analyze the query complexity of Aided Measured Continuous Greedy (Alg. 3) proposed by Buchbinder and Feldman [6] , which is O n 11 log(n) .In Alg. 3, queries to the oracle f only occur on Line 5. For each element u in the ground set U, r = 48n 6 log(2n) queries are made. These queries correspond to r independent samples of R(y(t)) to estimate E [∆(u|R(y(t)))]. Therefore, there are nr = O n 7 log(n) queries for each iteration of the while loop (Line 3-11). Time variable t is increased by δ1 = t s • n -4 , when t < t s , and is increased by δ2 = (1 -t s ) • n -4 , when t ≥ t s . Thus, there are a total of 2n 4 iterations within the while loop. In conclusion, the total number of queries made by the algorithm is O n 11 log(n) .In this section, we provide a detailed analysis of our randomized approximation algorithm and its two components, FASTLS and GUIDEDRG. This section is organized as follows: Appendix C.1 analyzes the theoretical guarantee of single run of FASTLS (Appendix C.1.1), which is needed to show that it finds a good guidance set. Then, although it is not needed for our results, we show the FASTLS independently achieves an approximation ratio achieved for SMCC under monotone and non-monotone objectives (Appendix C.1.2).In Appendix C.2, we provide pseudocode and formally prove the results for GUIDEDRG. Specifically, we solve the recurrences for both size and matroid constraint. Procedure FASTLS (f, I(M), Z 0 , ε): Input: oracle f , matroid constraint I(M),)/ε) queries such that f (S ∪ Z) + f (S ∩ Z) < (2 + ε)f (Z), where S ∈ I(M). Corollary C.1. Let Z be the solution of FASTLS (f, I(M), Z 0 , ε). If f (Z) < αOPT, Z is a ((1 + ε)α, α)-guidance set. Proof of Corollary C.1. By Lemma 2.2, let S = O and S = O ∩ Z respectively, it holds that f (O ∪ Z) + f (O ∩ Z) < (2 + ε)f (Z) , f (O ∩ Z) < (1 + ε)f (Z) . If f (Z) < αOPT, then f (O ∪ Z) + f (O ∩ Z) < (2 + ε)αOPT, f (O ∩ Z) < (1 + ε)αOPT. By Definition 2.1, Z is a ((1 + ε)α, α)-guidance set.In the following, we prove Lemma 2.2 for Alg. 4.Proof of Lemma 2.2. Query Complexity. For each successful replacement of elements on Line 6, it holds that ∆(e|Z) -∆(a|Z -a) ≥ ε k f (Z). By submodularity, f (Z -a + e) -f (Z) = ∆(e|Z -a) -∆(a|Z -a) ≥ ∆(e|Z) -∆(a|Z -a) ≥ ε k f (Z) .Hence, the oracle value f (Z) is increased by a factor of at least (1 + ε/k) after the swap. Therefore, there are at most log 1+ε/kf (O) f (Z0)iterations, since otherwise, it would entail f (Z) > f (O), which contradicts the fact that O is the optimal solution. Then, since the algorithm makes at most O (n) queries at each iteration, the query complexity can be bounded as follows,# queries ≤ O n log 1+ε/k f (O) f (Z 0 ) ≤ O n k ε log 1 α (f (Z 0 ) ≥ αf (O); Lemma A.4)Objective Value. For any S ∈ I(M), we consider adding dummy elements into S until |S| = k. By Lemma A.1, we consider Z and S are bases of matroid M with or without dummy elements.Then, by Lemma A.2, there exits a bijection σ : S \ Z → Z \ S such that Z + e -σ(e) is a basis for all e ∈ S \ Z. After the algorithm terminates, for every e ∈ S \ Z, it holds that,∆(e|Z) -∆(σ(e)|Z -σ(e)) < ε k f (Z). Then, εf (Z) > e∈S\Z ∆(e|Z) - a∈Z\S ∆(a|Z -a) Let ℓ = |S \ Z| = |Z \ S|, S \ Z = {e 1 , . . . , e ℓ }, Z \ S = {a 1 , . . . , a ℓ }. By submodularity, e∈S\Z ∆(e|Z) = (f (Z + e 1 ) -f (Z)) + (f (Z + e 2 ) -f (Z)) + . . . + (f (Z + e ℓ ) -f (Z)) ≥ (f (Z + e 1 + e 2 ) -f (Z)) + (f (Z + e 3 ) -f (Z)) + . . . + (f (Z + e ℓ ) -f (Z)) ≥ . . . ≥ f (Z + e 1 + . . . + e ℓ ) -f (Z) = f (S ∪ Z) -f (Z) . Also by submodularity, a∈Z\S ∆(a|Z -a) = ℓ i=1 ∆(a i |Z -a i ) ≤ ℓ i=1 ∆(a i |Z -a 1 -. . . -a i ) = f (Z) -f (S ∩ Z) Thus, εf (Z) > f (S ∪ Z) -f (Z) -(f (Z) -f (S ∩ Z)) ⇒(2 + ε)f (Z) > f (S ∪ Z) + f (S ∩ Z) .In this section, we show that FASTLS can be employed independently to achieves approximation ratios of nearly 1/2 and 1/4 for both the monotone and non-monotone versions of the problem, respectively.Monotone submodular functions. By employing FASTLS once, it returns an 1 2+ε -approximation result in monotone cases. Theorem C.1. Let ε > 0, and let (f, I(M)) be an instance of SM, where f is monotone. The input set Z 0 is an α 0 -approximate solution to (f, I(M)). FASTLS (Alg. 4) returns a solution Z such thatf (Z) ≥ f (O) /(2 + ε) with O (kn log(1/α 0 )/ε) queries. Proof. By Lemma 2.2, set S = O, it holds that (2 + ε)f (Z) > f (O ∪ Z) + f (O ∩ Z) ≥ f (O) ,where the last inequality follows by monotonicity and non-negativity.Non-monotone submodular functions. For the non-monotone problem, 2 repetitions of FASTLS (Alg. 5) yields a ratio of 1 4+2ε . The theoretical guarantees and the corresponding analysis are provided as follows. We remark that this is a primitive implementation of the guiding idea: the second run of FASTLS avoids the output of the first one. Input: oracle f , constraint I, an approximation result Z 0 , switch point t, error rate ε Z 1 ← FASTLS(f, U, I, Z 0 , ε) / * run FA S TLS with ground set U * / Z 2 ← FASTLS(f, U \ Z 1 , I, Z 0 , ε) / * run FA S TLS with ground set U \ Z 1 * / return Z ← arg max{f (Z 1 ) , f (Z 2 )}Theorem C.2. Let ε > 0, and let (f, I(M)) be an instance of SM, where f is not necessarily monotone. The input set Z 0 is an α 0 -approximate solution to (f, I(M)). Alg. 5 returns a solution Z such that f (Z) ≥ f (O) /(4 + 2ε) with O (kn log(1/α 0 )/ε) queries.Proof. By repeated application of Lemma 2.2 for the two calls of FASTLS in Alg. 5, it holds thatf (O ∪ Z 1 ) + f (O ∩ Z 1 ) < (2 + ε)f (Z 1 ) f ((O \ Z 1 ) ∪ Z 2 ) + f ((O \ Z 1 ) ∩ Z 2 ) < (2 + ε)f (Z 2 )By summing up the above two inequalities, it holds that EQUATIONfor i ← 1 to k do if i ≤ t • k then M i ← arg max M ⊆U \(Ai-1∪Z),M is a basis a∈M ∆(a|A i-1 ) else M i ← arg max M ⊆U \Ai-1,M is a basis a∈M ∆(a|A i-1 )if I represents the size constraint then 8 a i ← randomly pick an element from M i 9 A i ← A i-1 + a i -e 0 / *A i ← A i-1 + e i -σ i (e i ) end return A kIn this section, we present the pseudocode for GUIDEDRG as Alg. 6. Then, we provide the detailed proof of Lemma 2.3 in Appendix C.2.1, which addresses size constraints. Finally, we analyze the algorithm under matroid constraints and provide the guarantees and its analysis in Appendix C.2.2.In Sec. 2.2, we introduce the intuition behind GUIDEDRG under size constraint. Below, we reiterate theoretical guarantees achieved by GUIDEDRG under size constraints and provide the detailed analysis. Lemma 2.3. With an input size constraint I and a ((1 + ε)α, α)-guidance set Z, GUIDE- DRG returns set A k with O (kn) queries, s.t. E [f (A k )] ≥ 2 -t -1 k 1 -1 k e t-1 -e -1 -(1 + ε)α 1 -1 k 2 e t-1 -e -1 -α 1 + 1-t 1-1 k e t-1 -2 -1 k e -1 f (O) .We provide the recurrence of f ((O \ Z) ∪ A i ), f (O ∪ A i ) and f (A i ) in Lemmata C.< i ≤ t • k, it holds that E [f ((O \ Z) ∪ A i )] ≥ 1 - 1 k E [f ((O \ Z) ∪ A i-1 )] + 1 k [f (O \ Z) -f (O ∪ Z)] , E [f (O ∪ A i )] ≥ 1 - 1 k E [f (O ∪ A i-1 )] + 1 k [f (O) -f (O ∪ Z)] . When t • k < i ≤ k, it holds that E [f (O ∪ A i )] ≥ 1 - 1 k E [f (O ∪ A i-1 )] Proof. At iteration i, condition on a given A i-1 . When i ≤ tk, A i-1 ∩ Z = ∅ and M i is selected out of A i-1 ∪ Z, so (O ∪ Z) ∩ ((O \ Z) ∪ A i-1 ∪ M i ) = O \ Z (3) ((O ∪ Z) ∩ (O ∪ A i-1 ∪ M i ) = O.(4) Then,EQUATIONEQUATIONEQUATIONWhen i > tk, it holds thatEQUATIONBy unconditioning A i-1 , the lemma is proved.EQUATIONBy unconditioning A i-1 , the lemma is proved.Proof of Lemma 2.3. It follows from Lemma C.3 and the closed form for a recurrence provided in Lemma A.3 that           E [f ((O \ Z) ∪ A i )] ≥ f (O \ Z) -1 -1 - 1 k i f (O ∪ Z) , ∀0 < i ≤ tk E [f (O ∪ A i )] ≥ 1 - 1 k i-⌊tk⌋ f (O) -1 -1 - 1 k ⌊tk⌋ f (O ∪ Z) , ∀tk < i ≤ k(5) With the above inequalities, we can solve the recursion in Lemma C.4 as follows,E f A ⌊tk⌋ (a) ≥ 1 -1 - 1 k ⌊tk⌋ f (O \ Z) -1 -1 - 1 k ⌊tk⌋ -t 1 - 1 k ⌊tk⌋-1 f (O ∪ Z) E [f (A k )] (b) ≥ 1 - 1 k k-⌊tk⌋ E f A ⌊tk⌋ + (1 -t) 1 - 1 k k-⌊tk⌋-1 f (O) -1 -1 - 1 k ⌊tk⌋ f (O ∪ Z) ≥ (1 -t) 1 - 1 k k-⌊tk⌋-1 f (O) + 1 - 1 k k-⌊tk⌋ -1 - 1 k k f (O \ Z) - 1 + 1 -t 1 -1 k 1 - 1 k k-⌊tk⌋ -2 - 1 k 1 - 1 k k-1 f (O ∪ Z) (Inequality (a)) ≥ (1 -t) 1 - 1 k (1-t)k f (O) + 1 - 1 k (1-t)k+1 -1 - 1 k k f (O \ Z) - 1 + 1 -t 1 -1 k 1 - 1 k (1-t)k -2 - 1 k 1 - 1 k k-1 f (O ∪ Z) (tk -1 < ⌊tk⌋ ≤ tk) ≥ (1 -t) 1 - 1 k e t-1 f (O) + 1 - 1 k 2 e t-1 -e -1 f (O \ Z) - 1 + 1 -t 1 -1 k e t-1 -2 - 1 k e -1 f (O ∪ Z) (nonnegativity;Lemma A.4) ≥ (1 -t) 1 - 1 k e t-1 f (O) + 1 - 1 k 2 e t-1 -e -1 (f (O) -f (O ∩ Z)) - 1 + 1 -t 1 -1 k e t-1 -2 - 1 k e -1 f (O ∪ Z) (submodularity) = 2 -t - 1 k 1 - 1 k e t-1 -e -1 f (O) - 1 - 1 k 2 e t-1 -e -1 f (O ∩ Z) - 1 + 1 -t 1 -1 k e t-1 -2 - 1 k e -1 f (O ∪ Z) ,where Inequality (a) and (b) follow from Inequality 5, Lemma C.4 and A.3.Algorithm 7: RANDOMGREEDY for MatroidProcedure RANDOMGREEDY (f, M):Input: oracle f , matroid constraint M Initialize: A 0 ← arbitrary basis in I(M) for i ← 1 to k do M i ← arg max S⊆U ,S is a basis x∈S ∆(x|A i-1 )σ ← a bijection from M i to A i-1x i ← a uniformly random element from M iA i ← A i-1 + x i -σ(x i ) end return A kDiscussion about Intuition behind GUIDEDRG under Matroid Constraints. The pseudocode for RANDOMGREEDY under matroid constraints is provided in Alg. 7. To deal with the feasibility for matroid constraints, Alg. 7 starts with an arbitrary basis and builds the solution by randomly swapping the elements in ground set with a candidate basis. The analysis of it proceeds according to two main recurrences.1) E [f (A i ) -f (A i-1 )] ≥ 1 k E [f (O ∪ A i-1 ) -2f (A i-1 )] ,2) We provide the updated recursions for f 5 and C.6 below. Then, the closed form of the solution value, derived from these lemmata, is presented in Lemma C.7. After that, we prove the approximation ratio of the randomized algorithm under matroid constraint. E [f (O ∪ A i )] ≥ 1 - 2 k E [f (O ∪ A i-1 )] + 1 k E [f (O) + f (O ∪ A i-1 ∪ M i )] .((O \ Z) ∪ A i ), f (O ∪ A i ) and f (A i ) in Lemma C.Lemma C.5. When 0 < i ≤ t • k, it holds that E [f ((O \ Z) ∪ A i )] ≥ 1 - 2 k E [f ((O \ Z) ∪ A i-1 )] + 1 k [2f (O \ Z) -f (O ∪ Z)] , E [f (O ∪ A i )] ≥ 1 - 2 k E [f (O ∪ A i-1 )] + 1 k [2f (O) -f (O ∪ Z)] . When t • k < i ≤ k, it holds that E [f (O ∪ A i )] ≥ 1 - 2 k E [f (O ∪ A i-1 )] + 1 k f (O) 0 k (a) 1 + e 2 4 f (O) f (O) [f (O A i )] [f (A i )] 0 k (b) 1 + e 2 4 f (O) f (O \Z) f (O) [f (O A i )] [f ((O \Z) A i )] 0 tk k (c) 1 + e 2 4 f (O) f (O \Z) f (O) [f (O A i )] [f ((O \Z) A i )] [f (A i )]((O \ Z) ∪ A i ),which is the value that the solution approaches with the guidance. The figure (c) shows the updated degradation with a switch point tk, where the algorithm starts with guidance and then switches to running without guidance. It demonstrates that even though the value of A i decreases initially when the selection starts outside of Z, it benefits from the improved degradation of f (O ∪ A i ) upon switching back to the original algorithm.Proof. When i ≤ tk, it holds thatEQUATION≥ 1 k [f ((O \ Z) ∪ A i-1 ∪ M i ) -f ((O \ Z) ∪ A i-1 ) + (k -1)f ((O \ Z) ∪ A i-1 ) + f (O \ Z)] (submodularity) ≥ 1 k [(k -2)f ((O \ Z) ∪ A i-1 ) + 2f (O \ Z) -f (O ∪ Z)](submodularity; nonnegativity)EQUATIONBy unconditioning A i-1 , the lemma is proved.Lemma C.6. When 0 < i ≤ t • k, it holds that E [f (A i )] -E [f (A i-1 )] ≥ 1 k (E [f ((O \ Z) ∪ A i-1 )] -2E [f (A i-1 )]) . When t • k < i ≤ k, it holds that E [f (A i )] -E [f (A i-1 )] ≥ 1 k (E [f (O ∪ A i-1 )] -2E [f (A i-1 )]) . Proof. Given A i-1 at iteration i. When i ≤ t • k, since O is a base, O \ (A i-1 ∪ Z)with dummy elements is also a base. It holds thatEQUATIONEQUATIONLemma C.7. With an input matroid constraint I and a ((1 + ε)α, α)-guidance set Z, GUIDEDRG returns set A k with O (kn) queries, s.t. E [f (A k )] ≥ 1 2 1 2 + 3 2 -t -1 k 1 -2 k e 2(t-1) -e -2 -(1 + ε)α 1 -2 k 2 e 2(t-1) -e -2 -α 1 2 + 1-t 1-2 k e 2(t-1) -3 2 -1 k e -2 f (O) .Proof. It follows from Lemma C.5 and the closed form for a recurrence provided in Lemma A.3 thatEQUATION) Then, by sovling the recursion in Lemma C.6 with the above inequalities, it holds thatEQUATIONwhere Inequality (a) and (b) follow from Inequality 6, Lemma C.6 and A.3.Proof of Theorem 2.1 under matroid constraint. Let (f, I) be an instance of SM, with optimal solution set O. If f (Z) ≥ (0.305 -ε)f (O) under matroid constraint, the approximation ratio holds immediately. Otherwise, by Corollary C.1, FASTLS returns a set Z which is an ((1+ε)α, α)-guidance set, where α = 0.305 -ε.By Lemma C.7 and Z is an ((1 + ε)α, α)-guidance set with α = 0.305 -ε,E [f (A k )] ≥ 1 2 1 2 + 3 2 -t -ε (1 -2ε)e 2(t-1) -e -2 -(0.305 -0.695ε) (1 -2ε) 2 e 2(t-1) -e -2 -(0.305 -ε) 1 2 + 1 -t 1 -2ε e 2(t-1) - 3 2 -ε e -2 f (O) (∀k ≥ 1 ε ) ≥ (0.305 -ε)f (O) . (t = 0.559)Algorithm 8: A guided INTERLACEGREEDY subroutine for matroid constraints.Procedure GUIDEDIG-M (f, I(M), Z, G, ℓ):Input: oracle f , matroid constraint M, guidance set Z, starting set G , set size ℓ Initialize: A, A 1 , . . . , A ℓ ← ∅ for i ← 1 to k do X i ← {x ∈ U \ (G ∪ A ∪ Z) : A + x ∈ I(M)} j * i , a * i ← arg max j∈[ℓ],x∈X ∆(x|G ∪ A j ) A ← A + a * i , A j * i ← A j * i + a * i end σ ← a bijection from G to A s.t. (G ∪ A j ) \ x∈Aj σ -1 (x) is a basis return (G ∪ A j ) \ x∈Aj σ -1 (x) : 1 ≤ j ≤ ℓThe algorithm for the size constraint closely resembles INTERLACEGREEDY in Chen and Kuhnle [11] . Hence, we provide the pseudocode (Alg. 9), guarantees, and analysis in Appendix D.1.1. In this section, we focus on presenting GUIDEDIG-M for matroid constraints as Alg. 8. This algorithm addresses the feasibility issue by incorporating INTERLACEGREEDY into matroid constraints. Moreover, while it compromises the approximation ratio over size constraint to some extent, it no longer has the drawback of low success probability, which the size-constrained version has.Algorithm overview. Under size constraints, INTERPOLATEDGREEDY [11] constructs the solution with ℓ iterations, where each iteration involves calling the INTERLACEGREEDY subroutine and adding k/ℓ elements into the solution. However, this approach is not applicable to matroid constaint due to the feasibility problem. Consequently, we propose GUIDEDIG-M for matroid constraints designed as follows: 1) consider adding a basis (k elements) A to ℓ solution sets, where each addition dominates the gain of a distinct element in O; 2) by exchange property, establish a bijection between the basis A and the starting set G; 3) delete elements in each solution set that are mapped to by the basis A. This procedure avoids the extensive guessing of GUIDEDIG-S for size constraints and reduces the number of potential solutions from ℓ(ℓ + 1) to ℓ. We provide the theoretical guarantees and the detailed analysis below. Lemma D.1. Let O ∈ I(M), and suppose GUIDEDIG-M(Alg. 8) is called with (f, M, Z, G, ℓ), where Z ∩ G = ∅. Then GUIDEDIG-M outputs ℓ candidate sets with O (ℓkn) queries. Moreover, a randomly selected set G ′ from the output satisfies that:1) E [f (G ′ )] ≥ 1 - 2 ℓ f (G) + 1 ℓ + 1 1 - 1 ℓ f ((O \ Z) ∪ G); 2) E [f (O ∪ G ′ )] ≥ 1 - 2 ℓ f (O ∪ G) + 1 ℓ (f (O) + f (O ∪ (Z ∩ G)) -f (O ∪ Z)) ; 3) E [f ((O \ Z) ∪ G ′ )] ≥ 1 - 2 ℓ f ((O \ Z) ∪ G) + 1 ℓ (f (O \ Z) + f ((O \ Z) ∪ (Z ∩ G)) -f (O ∪ Z)) .Proof. A = {a * 1 , a * 2 , . . . , a * k } be the sequence with the order of elements being added. Since A and O \Z are basis of M (by adding dummy elements into O \Z), we can orderO \Z = {o 1 , o 2 , . . . , o k } s.t. for any 1 ≤ i ≤ k, {a * 1 , . . . , a * i-1 , o i } is an independent set. Thus, o i ∈ X i . Let A (i)j be A j after i-th iteration. Therefore, for any 1 ≤ j ≤ ℓ, by submodularity,∆(o i |G ∪ A j ) ≤ ∆ o i |G ∪ A (i-1) j ≤ ∆ a * i |G ∪ A (i-1) j * i ⇒ f ((O \ Z) ∪ G ∪ A j )-f (G ∪ A j ) ≤ k i=1 ∆(o i |G ∪ A j ) ≤ k i=1 ∆ a * i |G ∪ A (i-1) j * i = ℓ l=1 ∆(A l |G)By summing up the above inequality with 1 ≤ j ≤ ℓ,(ℓ + 1) ℓ j=1 ∆(A j |G) ≥ ℓ j=1 f ((O \ Z) ∪ G ∪ A j ) -ℓf (G) ≥ (ℓ -1)f ((O \ Z) ∪ G) + f ((O \ Z) ∪ G ∪ A) -ℓf (G) ≥ (ℓ -1)f ((O \ Z) ∪ G) -ℓf (G) (nonnegativity)Then, we can prove the first inequality as follows,E [f (G ′ ) -f (G)] = 1 ℓ ℓ j=1 f G \ σ -1 (A j ) ∪ A j -f (G) ≥ 1 ℓ ℓ j=1 ∆(A j |G) + f G \ σ -1 (A j ) -f (G) ≥ 1 ℓ + 1 1 - 1 ℓ f ((O \ Z) ∪ G) - 1 ℓ + 1 f (G) - 1 ℓ f (G) ⇒ E [f (G ′ )] ≥ 1 - 2 ℓ f (G) + 1 ℓ + 1 1 - 1 ℓ f ((O \ Z) ∪ G)By submodularity, nonnegativity, and Z ∩ A = ∅, the last two inequalities can be proved as follows,E [f (O ∪ G ′ )] = 1 ℓ ℓ j-1 f O ∪ G \ σ -1 (A j ) ∪ A j ≥ 1 ℓ ℓ j-1 ∆(A j |O ∪ G) + f O ∪ G \ σ -1 (A j ) ≥ 1 ℓ (f (O ∪ G ∪ A) -f (O ∪ G) + (ℓ -1)f (O ∪ G) + f (O)) ≥ 1 - 2 ℓ f (O ∪ G) + 1 ℓ (f (O) + f (O ∪ (Z ∩ G)) -f (O ∪ Z)) E [f ((O \ Z) ∪ G ′ )] = 1 ℓ ℓ j-1 f (O \ Z) ∪ G \ σ -1 (A j ) ∪ A j ≥ 1 ℓ ℓ j-1 ∆(A j |(O \ Z) ∪ G) + f (O \ Z) ∪ G \ σ -1 (A j ) ≥ 1 ℓ (f ((O \ Z) ∪ G ∪ A) -f ((O \ Z) ∪ G) + (ℓ -1)f ((O \ Z) ∪ G) + f ((O \ Z))) ≥ 1 - 2 ℓ f ((O \ Z) ∪ G) + 1 ℓ (f (O \ Z) + f ((O \ Z) ∪ (Z ∩ G)) -f (O ∪ Z))In this section, we provide the pseudocode, guarantees and analysis of GUIDEDIG-S, which highly resembles INTERLACEGREEDY in Chen and Kuhnle [11] . Lemma D.2. Let O ⊆ U be any set of size at most k, and suppose GUIDEDIG-S(Alg. 9) is called with (f, k, Z, G, ℓ). Then GUIDEDIG-S outputs ℓ(ℓ + 1) candidate sets with O (ℓkn) queries. Moreover, with a probability of (ℓ + 1) -1 , a randomly selected set A from the output satisfies that:1) E [f (A)] ≥ 1 ℓ + 1 E [f ((O \ Z) ∪ A)] + ℓ ℓ + 1 f (G) ; 2) E [f (O ∪ A)] ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ (f (O ∪ (Z ∩ G)) -f (O ∪ Z)) 3) E [f ((O \ Z) ∪ A)] ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ (f ((O \ Z) ∪ (Z ∩ G)) -f (O ∪ Z)).Algorithm 9: A (≈ℓ)-approximation that interlaces ℓ greedy procedures together and uses only 1/ℓ fraction of the budget.Procedure GUIDEDIG-S (f, k, Z, G, ℓ):Input: oracle f , constraint k, guidance set Z, starting set G , set size ℓ {a 1 , . . . , a ℓ } ← top ℓ elements in U \ (G ∪ Z) with respect to marginal gains on G for u ← 0 to ℓ in parallel do if u = 0 then 6 A u,l ← G ∪ {a l }, for all 1 ≤ l ≤ ℓ else 8 A u,l ← G ∪ {a u }, for any 1 ≤ l ≤ ℓ end for j ← 1 to k/ℓ -1 do 11 for i ← 1 to ℓ do 12 x j,i ← arg max x∈U \Z\(∪ ℓ l=1 A j u,l ) ∆(x|A u,i ) 13 A u,i ← A u,i ∪ {x j,i } 14 end end end return {A u,i : 1 ≤ i ≤ ℓ, 0 ≤ u ≤ ℓ}Proof. Let o max = arg max o∈O\(G∪Z) ∆(o|G), and let {a 1 , . . . , a ℓ } be the largest ℓ elements of {∆(x|G) : x ∈ U \ (G ∪ Z)}, as chosen on Line 3. We consider the following two cases.Case (O \ (G ∪ Z)) ∩ {a 1 , . . . , a ℓ } = ∅. Then, o max ̸ ∈ {a 1 , . . . , a ℓ } which implies that ∆(a u |G) ≥ ∆(o|G), for every 1 ≤ u ≤ ℓ and o ∈ O \ (G ∪ Z); and, after the first iteration of the for loop on Line 10 of Alg. 9, none of the elements in O \ (G ∪ Z) is added into any of {A 0,i } ℓ i=1 . We will analyze the iteration of the for loop on Line 4 with u = 0.Since none of the elements in O \ (G ∪ Z) is added into the collection when j = 0, we can order O \ (G ∪ Z) = {o 1 , o 2 , . . .} such that the first ℓ elements are not selected in any set before we get to j = 1, the next ℓ elements are not selected in any set before we get to j = 2, and so on. Let i ∈ {1, . . . , ℓ}. Let A j 0,i be the value of A 0,i after j elements are added into it, and define A 0,i = A k/ℓ 0,i , the final value. Finally, denote by δ j the value ∆ x j,i |A j 0,i . Then,f ((O \ Z) ∪ A 0,i ) -f (A 0,i ) ≤ o∈O\(A0,i∪Z) ∆(o|A 0,i ) (submodularity) ≤ o∈O\(G∪Z) ∆(o|A 0,i ) (G ⊆ A 0,i ) ≤ ℓ l=1 ∆ o l |A 0 0,i + 2ℓ l=ℓ+1 ∆ o l |A 1 0,i + . . . (submodularity) ≤ ℓ k/ℓ j=1 δ j = ℓ(f (A 0,i ) -f (G)),where the last inequality follows from the ordering of O and the selection of elements into the sets. By summing up the above inequality with all 1 ≤ i ≤ ℓ, it holds that,E [f (A)] = 1 ℓ ℓ i=1 f (A 0,i ) ≥ 1 ℓ(ℓ + 1) ℓ i=1 f ((O \ Z) ∪ A 0,i ) + ℓ ℓ + 1 f (G) = 1 ℓ + 1 E [f ((O \ Z) ∪ A)] + ℓ ℓ + 1 f (G) ,Since A 0,i1 ∩ A 0,i2 = G for any 1 ≤ i 1 ̸ = i 2 ≤ ℓ, and each x j,i is selected outside of Z, by repeated application of submodularity, it can be shown thatE [f ((O \ Z) ∪ A)] = 1 ℓ ℓ i=1 f ((O \ Z) ∪ A 0,i ) ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ f (O \ Z) ∪ ∪ ℓ i=1 A 0,i ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ (f ((O \ Z) ∪ (Z ∩ G)) -f (O ∪ Z)) E [f (O ∪ A)] = 1 ℓ ℓ i=1 f (O ∪ A 0,i ) ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ f O ∪ ∪ ℓ i=1 A 0,i ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ (f (O ∪ (Z ∩ G)) -f (O ∪ Z)) .Therefore, if we select a random set from {A 0,i : 1 ≤ i ≤ ℓ}, the three inequalities in the Lemma hold and we have probability 1/(ℓ + 1) of this happening.Case (O \ (G ∪ Z)) ∩ {a 1 , . . . , a ℓ } ̸ = ∅.Then o max ∈ {a 1 , . . . , a ℓ }, so a u = o max , for some u ∈ 1, . . . , ℓ. We analyze the iteration u of the for loop on Line 4. Similar to the previous case, let i ∈ {1, . . . , ℓ}, define A j u,i be the value of A u,i after we add j elements into it, and we will useA u,i for A k/ℓ u,i , Also, let δ j = ∆ x j,i |A j-1 u,i . Finally, let x 1,i = a u and observe A 1 u,i = G ∪ {a u }, for any i ∈ {1, . . . , ℓ}.O \ G = {o 1 , o 2 , . . .} such that: 1) for the first ℓ elements {o l } ℓ l=1 , ∆(o l |G) ≤ ∆(o max |G) = δ 1 ; 2) the next ℓ elements {o l } 2ℓl=ℓ+1 are not selected by any set before we get to j = 2, which implies that ∆ o l |A 1 u,i ≤ δ 2 , and so on. Therefore, analagous to the the previous case, we have thatEQUATIONSince, A u,i1 ∩ A u,i2 = G ∪ {a u } for any 1 ≤ i 1 ̸ = i 2 ≤ ℓ, a u ∈ O \ Z, and each x j,i is selected outside of Z, by submodularity and nonnegativity of f , it holds thatE [f ((O \ Z) ∪ A)] = 1 ℓ ℓ i=1 f ((O \ Z) ∪ A u,i ) ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ f (O \ Z) ∪ ∪ ℓ i=1 A u,i ≥ 1 - 1 ℓ f ((O \ Z) ∪ G) + 1 ℓ (f ((O \ Z) ∪ (Z ∩ G)) -f (O ∪ Z)) E [f (O ∪ A)] = 1 ℓ ℓ i=1 f (O ∪ A u,i ) ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ f O ∪ ∪ ℓ i=1 A u,i ≥ 1 - 1 ℓ f (O ∪ G) + 1 ℓ (f (O ∪ (Z ∩ G)) -f (O ∪ Z)) .Therefore, if we select a random set from {A u,i : 1 ≤ i ≤ ℓ}, the three inequalities in the lemma holds, and this happens with probability (ℓ + 1) -1 .In this section, we provide the randomized version (Alg 10) of our deterministic algorithm (Alg. 11, provided in Appendix D). The deterministic version simply evaluates all possible paths and returns the best solution. In the following, we provide the theoretical guarantee and its analysis under different constraints.Algorithm 10: The randomized algorithm suitable for derandomization.Input: oracle f , constraint I, an approximation result Z 0 , switch point t, error rate ε Z ← FASTLS(f, I, Z 0 , ε) Initialize ℓ ← 10 9ε , A 0 ← ∅ if I is a size constraint then for i ← 1 to ℓ do if i ≤ tℓ then A i ← a random set in GUIDEDIG-S(f, I, Z, A i-1 , ℓ) elseA i ← a random set in GUIDEDIG-S(f, I, ∅, A i-1 , ℓ) end else for i ← 1 to ℓ do if i ≤ tℓ then A i ← a random set in GUIDEDIG-M(f, I, Z, A i-1 , ℓ) else A i ← a random set in GUIDEDIG-M(f, I, ∅, A i-1 , ℓ) end end return A * ← arg max{f (Z), f (A ℓ )}Theorem D.3. Let (f, I) be an instance of SM, with the optimal solution set O. Algorithm 10 achieves an expected (0.385 -ε) approximation ratio with (ℓ + 1) -ℓ success probability and input t = 0.372 under size constraint, where ℓ = 10 9ε . Moreover, it achieves an expected (0.305 -ε) approximation ratio with t = 0.559 under matroid constraint. The query complexity of the algorithm is O (kn/ε).By Lemma D.2 in Appendix D.1.1 and the closed form for a recurrence provided in Lemma A.3, the following corollary holds, Corollary D.1. After iteration i of the for loop in Alg. 10, the following inequalities hold with a probability of (ℓ + 1)-i E [f (A i )] ≥ ℓ ℓ + 1 E [f (A i-1 )] + 1 ℓ + 1 f (O \ Z) -1 -1 - 1 ℓ i f (O ∪ Z) , 1 ≤ i ≤ tℓ E [f (A i )] ≥ ℓ ℓ + 1 E [f (A i-1 )] + 1 ℓ + 1 1 - 1 ℓ i-⌊tℓ⌋ f (O) -1 -1 - 1 ℓ ⌊tℓ⌋ f (O ∪ Z) , tℓ < i ≤ ℓ Proof of approximation ratio. If f (Z) ≥ (0.385 -ε)f (O), the approximation ratio holds immediately. So, we analyze the case f (Z)< (0.385 -ε)f (O) in the following. Recall in Corollary C.1 that Z is a (1 + ε)α, α)-guidance set, it holds that f (O ∪ Z) + f (O ∩ Z) < (0.77 -1.615ε)f (O) and f (O ∩ Z) < (0.385 -0.615ε)f (O).By repeatedly implementing Lemma A.3 with the recursion in Corollary D.1, it holds thatE f A ⌊tℓ⌋ ≥ 1 -1 - 1 ℓ + 1 ⌊tℓ⌋ (f (O \ Z) -f (O ∪ Z)) + ⌊tℓ⌋ ℓ + 1 1 - 1 ℓ ⌊tℓ⌋ f (O ∪ Z) ≥ 1 -1 - 1 ℓ + 1 ⌊tℓ⌋ (f (O) -f (O ∩ Z) -f (O ∪ Z)) + ⌊tℓ⌋ ℓ + 1 1 - 1 ℓ ⌊tℓ⌋ f (O ∪ Z) (submodularity) E [f (A ℓ )] ≥ 1 - 1 ℓ + 1 ℓ-⌊tℓ⌋ E f A ⌊tℓ⌋ + ℓ -⌊tℓ⌋ ℓ + 1 1 - 1 ℓ ℓ-⌊tℓ⌋ f (O) -1 -1 - 1 ℓ ⌊tℓ⌋ f (O ∪ Z) ≥ 1 - 1 ℓ + 1 (1-t)ℓ+1 -1 - 1 ℓ + 1 ℓ (f (O) -f (O ∩ Z) -f (O ∪ Z)) + tℓ ℓ + 1 1 - 1 ℓ + 1 (1-t)ℓ+1 1 - 1 ℓ tℓ f (O ∪ Z) + (1 -t) 1 - 1 ℓ + 1 1 - 1 ℓ (1-t)ℓ+1 f (O) -1 -1 - 1 ℓ tℓ-1 f (O ∪ Z) (tℓ -1 < ⌊tℓ⌋ ≤ tℓ) = 1 - 1 ℓ + 1 1 - 1 ℓ + 1 (1-t)ℓ -1 + 1 ℓ 1 - 1 ℓ + 1 ℓ+1 (f (O) -f (O ∩ Z) -f (O ∪ Z)) + t • ℓ -1 ℓ + 1 1 - 1 ℓ + 1 1 - 1 ℓ + 1 (1-t)ℓ 1 - 1 ℓ tℓ-1 f (O ∪ Z) + (1 -t) 1 - 1 ℓ + 1 2 1 - 1 ℓ 1 - 1 ℓ (1-t)ℓ-1 f (O) -1 - 1 ℓ (1-t)ℓ f (O ∪ Z) + 1 - 1 ℓ 1 - 1 ℓ ℓ-1 f (O ∪ Z) ≥ 1 - 1 ℓ e t-1 -e -1 (f (O) -f (O ∩ Z) -f (O ∪ Z)) + t • 1 - 1 ℓ 3 e -1 f (O ∪ Z) + (1 -t) 1 - 1 ℓ 2 1 - 1 ℓ e t-1 f (O) -e t-1 f (O ∪ Z) + 1 - 1 ℓ e -1 f (O ∪ Z) (f (O) -f (O ∩ Z) -f (O ∪ Z) > 0; nonnegativity; Lemma A.4) ≥ c(c 2 (1 -t) + 1)e t-1 -e -1 f (O) -c(c(1 -t) + 1)e t-1 -(c 3 + 1)e -1 (f (O ∪ Z) + f (O ∩ Z)) -c 3 e -1 -c 2 (1 -t)e t-1 f (O ∩ Z) (Let c = 1 -9ε 10 = 1 -1 ℓ ) ≥ c(c 2 (1 -t) + 1)e t-1 -e -1 f (O) -c(c(1 -t) + 1)e t-1 -(c 3 + 1)e -1 (0.77 -1.615ε)f (O) -c 3 e -1 -c 2 (1 -t)e t-1 (0.385 -0.615ε)f (O) (f (O ∪ Z) + f (O ∩ Z) < (0.77 -1.615ε)f (O); f (O ∩ Z) < (0.385 -0.615ε)f (O)) ≥ (0.385 -ε)f (O) (0 < ε < 0.385; t = 0.372) D.2. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The research conforms in every respect to the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [No] Justification: Ours is foundational research, not tied to any particular application or deployment. The applications upon which we implemented and empirically evaluated our algorithms are proof-of-concept and thus our provided implementations are unlikely to lead directly to negative societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: We do not release any data or models that have a high risk for misuse. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: The only pre-existing asset used is the video in the summarization experiment. We explicitly mention the license in Appendix F and properly respect the terms. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The released source code is well documented.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Our code is available at https://gitlab.com/luciacyx/guided-rg.git. 
 
 Appendix:  


Decision: The main contribution of the paper are combinatorial algorithms for constrained submodular maximization that achieve an approximation guarantee that is better than 1/e.  Several algorithms have been proposed that achieve such a guarantee, but they are continuous algorithms based on the multilinear extension relaxation and are generally inefficient in practice. In contrast, the proposed algorithms are combinatorial and thus have the potential to be much more practical. There was consensus among the reviewers that this is a strong contribution to this classical problem. One of the reviewers noted several issues with the paper's presentation and the authors promised to address them in the revised version.

Reviews: review: paper_summary: paper_summary: The paper investigates combinatorial approximation algorithms for constrained submodular maximization problems. Observing the algorithms that pass the $1/e$ threshold are generally carries the problem to the continuous domain, they investigate the answer to the following question: "Is it possible to obtain approximation ratios that are better than $1/e$ for constrained submodular maximization problems with combinatorial algorithms?" They answer this question affirmatively by combining Buchinder et al.'s RandomGreedy algorithm with a novel fast local search algorithm. Additionally, they propose derandomized versions of these algorithms by altering the InterpolatedGreedy algorithm by Chen and Kuhnle.
strength_weakness: strength_weakness: - On lines 73-75, you mention "Unfortunately, there is no known method to derandomize continuous algorithms, as the only known way to approximate the multilinear extension relies on random sampling methods." You may want to revise this sentence because as far as I know, there is a work that proposes estimating the multilinear relaxation of coverage-like functions with Taylor series expansions instead of sampling. Citation: Özcan, Gözde, Armin Moharrer, and Stratis Ioannidis. "Submodular maximization via Taylor series approximation." Proceedings of the 2021 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 2021.

- On line 283, you mention an InterlaceGreedy algorithm for the first time as far as I can tell. Is this a typo or a different algorithm? If it is a different algorithm, where it is described?
questions: questions: - On lines 114-115, you mention using an LP method for derandomizing the RandomGreedy algorithm and how this method did not work in this case. Could you please elaborate more on why this was the case? Was the problem asymptotic query complexity or something else?

- Why the dummy elements are needed?

-
limitations: limitations: Both in Sections 1.1 and 5, the authors discuss the limitations of their work fairly.
paper_summary: paper_summary: This paper studies the classical problem of maximizing a non-monotone submodular function subject to a cardinality and a matroid constraint.
A long line of work has developed approximation algorithms for these problems which achieve a 0.401approximation; however, every algorithm which achieves better than $1/e = 0.368$ relies on the multilinear extension and is primarily of theoretical interest, as the run times are very large (but polynomial).
The more practical combinatorial algorithms have not been able to break the $1/e$ barrier.

The main contribution is a suite of algorithms which work via an "guided" local search procedure.
The main algorithm works as follows: a local search algorithm obtains a first solution and then an "guided" local search uses this first solution to obtain a second one. 
If the parameters of the algorithm is appropriately set, at least one of these two solutions is of high (expected) quality.
The main result is that this (randomized) algorithm achieves a $0.385-\epsilon$-approximation for cardinality constraint and $0.305-\epsilon$ approximation for matroid constraint and runs in $\mathcal{O}(n k / \epsilon)$ time.

There are a variety of other results, including several de-randomizations of this algorithm, though those are mostly of theoretical interest because their run time is exponential in $\epsilon$.
Simulations are run comparing the algorithms to two reasonable benchmarks.
strength_weakness: strength_weakness: **Paper Clarity**: For the most part, the paper is not well organized and can be challenging to read. With the exception of Section 2.2, the writing is a bit rushed and lacking focus. Many times I had to go back and forth in the paper just to read it. Perhaps the reason for this is that several algorithms are being presented with various guarantees and settings. While the results are great, the paper requires some serious efforts in improving the readability.

**Simulations**: While I appreciate the authors' work in constructing simulations, they are admittedly quite weak or at the very least poorly explained. This may be due in large part to space constraints. I summarize the issues here:

- The objective functions are not presented and the movie summarization dataset is not discussed.
- It is claimed that max-cut is run on 3 different random graph models -- but then how does only one line appear in the Figure 3c?
- If FastLS + GuidedRG is random, then why does it not also have some uncertainty quantification (i.e. standard error bars) on its objective value and run time?
- The simulations are weak because in all of these instances, the more sophisticated algorithms provide very little improvement over the greedy algorithm. I'm sympathetic to this phenomenon, I know it can happen. But then I think that the experiments should focus on practical instances where the sophisticated algorithms do actually improve over the greedy algorithm.
questions: questions: I thank the authors for their manuscript and invite them to respond to the points raised in my review. 
However, I do not feel that I have any questions to raise at this time.
limitations: limitations: All limitations sufficiently addressed.
paper_summary: paper_summary: In this paper, the authors develop a combinatorial algorithm for non-monotone submodular maximization under both size and matroid constraints. Their algorithm uses local search to guide RANDOM GREEDY and INTERPOLATEDGREEDY, providing both a randomized algorithm and a deterministic algorithm. For size constraints, the algorithm achieves an approximation ratio of 0.385, and for matroid constraints, it achieves an approximation ratio of 0.305. It is the first combinatorial algorithm with an approximation ratio greater than 1/e for size constraints. The technique in this paper is similar to that in [6]. However, while the algorithm in [6] is a continuous algorithm requiring a query complexity of $\Omega(n^{10}) $, the algorithm presented in this paper only requires $O(kn)$ queries of a value oracle. They also propose another algorithm based on this approach, which replaces the greedy part in INTERPOLATEDGREEDY with the descending thresholds technique. This algorithm achieves an approximation ratio of 0.377 for size constraints in nearly linear query time $O(k \log n)$, which is slightly greater than 1/e.
strength_weakness: strength_weakness: 1.	The results in the paper are not strong enough. For the randomized algorithm, the paper an algorithm with query complexity $O(kn/\epsilon)$ and approximation ratio 0.385. It is worse than the most recent paper (https://arxiv.org/abs/2405.13994). For two deterministic algorithms, they are impractical since the dependence of $\epsilon$ is too large.
questions: questions: Both the results and techniques in this paper are somewhat similar to those in the recent paper (https://arxiv.org/abs/2405.13994). It might be beneficial to explain the relationship between your paper and theirs, especially the difference in the techinique ideas.
limitations: limitations: Yes
paper_summary: paper_summary: This paper studies the fundamental problem of improving the approximation factor for non-monotone submodular maximization subject to cardinality or matroid constraints. In particular, the focus of the work is on designing combinatorial algorithms as opposed to continuous methods based on the multilinear extension. 

The paper has the following contributions:
for cardinality constraints:
- a combinatorial $0.385 - \varepsilon$ approximation is proposed, which runs in $O(nk/\varepsilon)$. The algorithm is randomized but can be derandomized with a multiplicative deterioration of the query complexity which is exponential in $1/\varepsilon$
- a deterministic $0.377 - \varepsilon$ approximation is obtained, with running time $O(n \log k\cdot C_{\varepsilon})$, where $C_{\varepsilon}$ is exponential in $1/\varepsilon$. 
- for context, the previous best combinatorial algorithm provided a $0.367$ approximation, while the overall state of the art is a continuous $0.41$-approximation. 
for matroid constraints: 
- a combinatorial $0.305 - \varepsilon$ approximation is proposed, which runs in $O(nk/\varepsilon)$. The algorithm is randomized but can be derandomized with a multiplicative deterioration of the query complexity, which is exponential in $1/\varepsilon$
- the previous best combinatorial algorithm provided a $0.283$ approximation, while the overall state of the art is a continuous $0.41$-approximation.
strength_weakness: strength_weakness: the deterministic algorithms are impractical, as they feature an exponential dependence on the approximation parameter $1/\varepsilon$. Their relevance is mainly theoretical.
questions: questions: None
limitations: limitations: The paper has no potential negative societal impact

Comments: title: response
response to authors
response to contemporaneous work
comment: Thank you for your response. I've increase my score.
Thank you for the feedback and for the specific example concerning the presentation. We agree that our style of introducing the final algorithm or result first, before defining each piece, is difficult to read. However, we believe we can significantly improve the readability without a large amount of reorganization. For example, when introducing Alg. 2, we can rephrase the description to give a better sense of what each component is, and also that their precise description is deferred:

> In overview, Alg. 2 consists of two components, which are detailed below. The first component is a local search algorithm described in detail in Section 2.1. In brief, the local search starts from a constant-factor solution and efficiently improves it to nearly a local optimum. The second component is a random greedy algorithm that is guided by the output of the local search, described in detail in Section 2.2...
 
In any case, thank you again for the feedback, and we will improve the readability in the next version.
I thank the authors for their thoughtful response to my review.

Their responses on the simulations have been satisfactory. I understand and agree with all points (except perhaps that 2% increase is significant, but we don’t have to discuss this further). I believe they will be addressed in a revision.

I understand that the space constraints make writing the paper difficult. I am not opposed to the idea of putting the size constraint in the main body and the matroid, together with all formal analysis in the appendix 

But let me be a bit more specific about the issue of clarity. The way I see it, the main algorithm of the paper is Algorithm 2. However, when the reader reads the pseudocode of Algorithm 2 on top of page 4, it conveys very little meaning about the algorithm itself. Namely, GuidedRG is not defined nearby in the paper (indeed, it is only defined in the appendix). So, as the reader, it is quite confusing to read Section 2.0 as the algorithms aren’t defined sufficiently well for us to have an understanding yet. A similar thing happens in Definitions 2.1 and Lemma 2.2 — these are outputs of an algorithm which is still unfamiliar to the reader at that point. In this way, the reader is having to skip back and forth between parts of the paper upon a first read, which does detract from the clarity. You might consider shortening or moving Sec 2.3 and 3 to the appendix to describe GuidedRG in the main paper.

I mention this only to be more specific about what I meant by paper clarity and offer suggestions for improvement.

I like the theoretical results quite a lot and I think that authors are capable of revising the paper so as to improve clarity. The only difficult is that such revisions appear to require non-trivial re-organization of the paper. As a reviewer, this puts me in a tough place. I am uneasy with significantly raising my score because the authors could revise the paper to make it clearer. We should be reviewing the submitted paper rather than the paper that could be resubmitted. This is especially true given that there is no way to accept only after verifying the appropriate revisions have been made. On the other hand, it would be a shame for the paper to not appear in this conference, given its strong technical results. I would also feel bad if rejection of this paper meant it would no longer be viewed as contemporary to Tukan et al (2024).

I will raise my score to weak accept to signal to the AC that I am supportive of the technical results in the paper, but still have concerns about the presentation.
I want to echo the authors on this point. I do not think it is appropriate to compare their results with results from work that was clearly done in parallel. Here is the NeurIPS policy on contemporaneous work. 

**Contemporaneous Work**: For the purpose of the reviewing process, papers that appeared online within two months of a submission will generally be considered "contemporaneous" in the sense that the submission will not be rejected on the basis of the comparison to contemporaneous work. Authors are still expected to cite and discuss contemporaneous work and perform empirical comparisons to the degree feasible. Any paper that influenced the submission is considered prior work and must be cited and discussed as such. Submissions that are very similar to contemporaneous work will undergo additional scrutiny to prevent cases of plagiarism and missing credit to prior work.