Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization
Authors: Yixin Chen
Ankur Nath
Chunli Peng
Alan Kuhnle
Venue: NeurIPS 2024 poster (2024)
Keywords: combinatorial algorithms
deterministic algorithms
submodular optimization
Primary area: optimization
TL;DR: First combinatorial algorithms for submodular maximization with ratio better than 1/e ≈ 0.367

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$.

Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization
Yixin Chen, Ankur Nath, Chunli Peng, Alan Kuhnle
Department of Computer Science & Engineering Texas A&M University
Colloge Station, TX
{ [chen777, anath, chunli peng, kuhnle| @tamu. edu
Abstract
For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than 1/c 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 simple randomized greedy algorithm of Buchbinder al. [9]: 1/e 0.367 for size constraint and 0.281 for the matroid constraint in (kn) queries, where & is the rank of the matroid. In this work, we develop the first combinatorial algorithms to break the 1/c barrier: we obtain approximation ratio of 0.385 in O (kn) queries to the submodular set function for size constraint, and 0.305 for general matroid constraint. These achieved by guiding the randomized greedy algorithm with a fast local search algorithm. Further, 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.
Introduction
A nonnegative set function f 24 - RR is submodular iff for all S C U. E u U (z)) 2 (T (x))-f(T): and fs monotone iff (S) ( for allall a CT Submodular optimization plays important role in data science and machine learning [3], particularly tasks that involve selecting 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 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 non-monotone, e,g. Mirzasoleiman et al. [23], Tschiatschek et al. [31]. Formally, study the optimization problem (SM). max f (S) S I, where f is nonnegative, submodular and not necessarily monotone; and I C 2 is a family of feasible subsets. Specifically, consider two cases: when I is size constraint (all sets of size at most k); and more generally, when I is an arbitrary matroid of rank
In this field, algorithms typically assume access to 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 (NcurIPS 2024).

---

Table 1: The prior state-of-the-ar and the ratios achieved in this paper, in each category: deterministic (det), randomized combinatorial (emb), and continuous (cts).
Constraint
Reference
Query
Ratio
Type
Buchbinder and Feldman [5]
O (k*")
1/e z 0.367
Det
Buchbinder al. [9]
O (kn)
I/e
Cmb
Buchbinder and Feldman [7]
(mly(n)
0.401
Cts
Size
Algorithm
(km/a)
0.385
Cmb
Algorithm 11
o km
992 10
20
0.385
Det
Algorithm 14
o (log(k)) (k))
0.377
Det
Sun al. [30]
(k3n²)
0.283 O (++
Det
Buchbinder et al. [9]
O (kn)
0.283
Cmb
Matroid
Buchbinder and Feldman [7]
poly(n)
0.401
Cts
Algorithm
(km/e)
0.305
Cmb
Algorithm 11
o km
20
0.305
Det
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 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/c ratio oracle queries the multilinear extension of submodular function and its gradient. The multilinear extension relaxes the submodular set function allow choosing an element with probability in [0, 1]. Although this is powerful technique, the multilincar extension must be approximated by polynomially many random samples of the original function oracle. Unfortunately, this leads high query complexity for these algorithms, which we term continuous algorithms; typically, the query complexity to the original submodular function 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' log(n)) to the set function oracle. Consequently, these algorithms are of mostly theoretical interest the time cost of running on tiny instances (say, < 100) is already prohibitive, as demonstrated by Chen and Kuhnle [12] where a continuous algorithm required more than 10 queries the set function on an instance with 87, k = 10.
For size and matroid constraints, the current state-of-the-arr approximation ratio for combinato- rial 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, and 0.283 - ratio for matroid constraint; its query complexity O (kn). Thus, there is no known com- binatorial algorithm that breaks the 1/e barrier; and therefore, no such algorithm available be used in practice on any of the applications of SM described above.
Algorithm 1: Buchbinder et al. [9]
Procedure RANDOMGREEDY (f, k):
Input: oracle f. size constraint Initialize: Ag <-
for i + to k do M₁ +
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 theoretical interest, de- terministic algorithms are desirable in practice, as ratio that holds in expectation may fail on any given run with constant probability. Buchbinder and Feld- man [5] introduced linear programming method to derandomize the R RANDOMGREEDY algorithm (at the expense of additional time complexity), meaning that the best known ratios for deterministic algo- rithms are again given by RANDOMGREEDY. There is no known method to derandomize continuous
arg max Exes A(x)A-1)
x + a uniformly random
element from M, A; + 4
end return As

---

algorithms, as the only known way to approximate the multilinear extension of a general submodular set function relies on random sampling methods. Özcan al. [26], however, introduced a determin- istic estimation via Taylor series approximation, but this approach is limited to a specific class of submodular functions that can expressed as weighted compositions of analytic and multilinear functions. Therefore, there is no known deterministic algorithm that breaks the 1/c 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? so, are the resulting algorithms practical and do they yield empirical improvements in objective value over existing algorithms?
1.1 Contributions
In this work, we improve the best known ratio for combinatorial algorithm for size-constrainge SM to 0.385 E ze 1/e + 0.018. This is achieved by using the result of a novel local search algorithm to guide the RANDOMGREEDY algorithm. Overall, obtain query complexity of O (kn/e), which is at worst quadratic in the size of the ground set, since l S n. Thus, this algorithm is practical and can on moderate instance sizes; the first algorithm with ratio beyond 1/c for which this is possible. Further, we extend this algorithm to the matroid constraint, where it improves the best known ratio of combinatorial algorithm for general matroid constraint from 0.283 of RANDOMGREEDY to 0.305 - E.
Secondly, we obtain these same approximation ratios with deterministic algorithms. The ideas similar to the randomized case, except we leverage a recently formulated algorithm INTERPOLATI EDGREEDY [11] replacement for guided RANDOMGREEDY. The analysis of INTERPOLATED GREEDY has similar recurrences (up to low order terms) and the algorithm can be guided a similar fashion to RANDOMGREEDY, but is amenable derandomization. The derandomization only adds constant factor, albeit one that is exponential in (1/e).
Next, we seek to lower the query complexity further, while still improving the 1/e ratio. As INTERPOLATEDGREDDY can be sped up to Os log k). the bottleneck becomes the local search procedure. Thus, we develop a faster way to produce the guiding set Z by exploiting run of (unguided) INTERPOLATEDGREEDO and demonstrating that a decent guiding set is produced the algorithm exhibits nearly worst-case behavior. With this method, we achieve deterministic algorithm with ratio 0.377 = 1/e + 0.01 in Oz Onnnoog log k) query complexity, which is nearly linear in the size of the ground set (since k- = (n)).
Finally, we demonstrate the practical utility of our combinatorial -pp8o-approximmation algorithm by implementing it and evaluating in the context of two applications of size-constrained SM on moderate instance sizes (up to n = 10a). We evaluate with parameters set to enforce a ratio > 1/e. It outperforms both the standard greedy algorithm and RANDOMGREEDY by significant margin terms of objective value; moreover, it uses about twice the queries of RANDOMGREEDY and orders of magnitude faster than existing local search algorithms.
1.2 Additional Related Work
Derandomization. Buchbinder and Feldman [5] introduced 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 RANDOM RANDOMGREEDY for matroids. disadvantage of this approach is an increase the query complexity over the original randomized guided RANDOMGREEDY
algorithm. Moreover, we attempted to this method to derandomize algorithm, but were unsuccessful. Instead, we obtained our deterministic algorithms by guiding the INTERPOLATEDGREEDY algorithm instead of RANDOMGREED this algorithm is casier to derandomize, notably without increasing the asymptotic query complexity.
Relationship to Buchbinder and Feldman [6]. The continuous, 0.385 1.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 R RANDOMGREEDY with the output of 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 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 algorithms. Local search is a technique widely used in combinatorial optimization. Nemhauser al. [25] introduced local search algorithm for monotone functions under size con- straint; 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. Feige et al. [14] proposed a 1/3 approximation algorithm with O (n*/s) queries for the unconstrained submodular maximization problem utilizing local search. Meanwhile, Lee et al. [21] proposed a local search algorithm for general SM with matroid constraint, attaining 1 E upproximation ratio with a query complexity of O (ke log (k) m//).. We propose our own FASTLS in Section 2.1, yielding a ratio of 1/2 for monotone cases and 1/4 for non-monotone cases through repeated applications of FASTLS, while running in O (kn/E) queries.
Fast approximation algorithms. Buchbinder et al. [10] developed a faster version of RANDOM- GREEDY for size constraint that reduces the query complexity to O₂ (n) with ratio of 1/e e. Chen and Kuhnle [11] proposed LINEARCARD, the first deterministic, linear-time algorithm with an 1/1L.657-approximatio ratio for size constraints. Also, Han al. [17] introduced TWINGREEDY, a 0.25-approximmaion 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 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 -ppsSaappoo algorithm. Both papers start from a similar idea-guiding the random greedy algorithm with 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 Og (n + k²). 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- - -e with Og (n log(k)) queries; and 3) derandomize these algorithms.
1.3 Preliminaries
Notation. In this section, establish the notations employed throughout the paper. We denote the marginal gain of adding A to B by A(A = (A B) f (B). ). For every set S C l and an element U, we denote S U {xr by S + xx, and 5 [x) by related feasible sets I, let O E arg max 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 eo is utilized to represent dummy element.
x. Given constraint and its
Submodularity. A set function f 2 + RR is submodular, if Axx|S) 2 ( for all SCTS U and u \ T, or equivalently, for all A, B S U, it holds that f (A) f (B) 2 f (AUB) I B).
Constraints. 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). where is an input parameter. The matroid constraint is defined in Appendix A.
Organization. Our randomized algorithms are described in Section 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 F. 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 (J,Z), I), a constant-factor approximation Zo. switch time E (0, 1]. accuracy
& 0
2 1 + FASTLS (f. I, Zo.
find local opt 2 */ /* guided by local optimun 2 x/
A < GUIDEDRG( ( Z, return arg max (Z), (Z),5(A)
2 A Randomized (0.385 -pappoxximaiionn in O (kn/E) Queries
In this section, we present our randomized approximation algorithm (Alg. 2) for both size and matroid constraints. This algorithm improves the state-of-the-arn combinatorial approximation ratio =
to 0.385 constraint.
1/e + 0.018 for size constraint, and to 0.305
0.283 + 0.022 for matroid
Algorithm Overview. In overview, Alg. 2 consists of two components, which are detailed below. The first component is a local search algorithm, FASTLS (Alg. 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 Zo as input, which may be produced by any approximation algorithm with better than O (km) query complexity. The second component is a random greedy algorithm, GUIDEDRG (Alg. 6 Appendix C.2), that is guided by the output of the local search, described in detail in Section 2.2. Also, GUIDEDRG G takes parameter t E [0, 1]. which is the switching time (as fraction of the budget or rank k) from guided to unguided behavior. The candidate with best value from the two subroutines is returned.
If f()) < aOPT (otherwise, there is nothing to show), then the local search set satisfies our definition of ((1 + E)a, -)-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 & O, and k 2 1/E. Algorithm 2 achieves an expected (0.385 appooooxiinaooonn ratio for size constraint with / = 0.372, and an expected (0.305 approxxiitiioo ratio for matroid constraint with = 0.559. The query complexity of the algorithm is O (km/E).
2.1 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/s) time complexity, where is the maximum size of a feasible set, and ε > 0 is an input accuracy parameter.
In overview, the algorithm maintains fcasible set Z: initially, Z Zo. where Zo is 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, compute A(a Z a); if a & Z, this is just the gain of a to Z: this requires O (n) queries. Then, if a E and & such that Z a a is feasible, and A(e) - A(a Z a) 2 {Z), then 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 + e/k) factor. Since f(Z) is initialized to a constant fraction of OPT. it follows that we make at most Okk/s) swaps. Since each swap requires O (n) queries, this yields the query complexity of the algorithm: (kn/s). In addition, if f is monotone, FASTLS gets ratio of nearly 1/2 for FASTLS. A second repetition of FASTLS yields 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 guidance set. Intuitively, a set Z is good guidance set it has low f-value and also ensures that the value of its intersection and union with an optimal solution are poor.
5

---

f(0)
f(0)
f10)
Ef uA
Elr UA)
E(flo u AMl
F(012)
F(0NZ)
=(f( A.
((())
1())
1())
EIRAN
El(((OZ)) UA))
E(FIM
(a)
(b)
(c)
Figure 1: (a): The evolution of [f (OU A.) and [ (A.)] in the worst of the analysis of RANDOMGREEDY, as the partial solution size increases to k. (b): Illustration of how the degradation of [ (O U A;)] changes as introduce an (0.385 + -.ud5)-guuddanc set. (c): The updated degradation with a switch point th, where the algorithm starts with guidance and then switches to running without guidance. The dashed curved lines depict the unguided values from (a).
Definition 2.1. A set Z is a (a, -)guudancce set, if given constants a, E (0,).5) and optimum solution O, it holds that: 1) f (Z) < af (0); (0 2) < af (O); 3) (OUZ) s BI (0), or alternatively, 3') (on Z) + (OU (a B)f
Lemma 2.2 (proved in Appendix C.1.1) implies that for the FASTLS output Z, if f(Z) < aOPT, then Z is ((1 + s)a, --gguidnece set.
Lemma 2.2. Let > 0. and let (J,I(M)) be an instance of SM. The input set Zo is oo- approximate solution to (f, (MM). FASTLS (Alg. 4) returns a solution Z with (kn log(1/on)/s) queries such that / (SU / (S 2) < (2 + e),f (Z), where S E I(M).
2.2 Guiding the RANDOMGREED Algorithm
In this section, we discuss the guided RANDOMGREEDY algorithm (Alg. using an ((1 + E)a, a)- guidance set Z returned by FASTLS. Due to space constraints, we only consider the size constraint in the main text. The ideas for the matroid constraint are similar, although the final recurrences obtained differ. The version for matroid constraints is given in Appendix C.2.2.
The algorithm GUIDEDRG is simple to describe: it maintains partial solution A. initially empty. takes as parameters the switching time and guidance set Z. While the partial solution satisfies |A| < Lk; the algorithm operates as RANDOMGREED" with ground set ti \ Z: after |A| 2 (k, it operates as RANDOMGRERDY with ground set U. Pseudocode is provided in Appendix C.2.
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:
[[S - (A:- [EISOOU (A:-
Intuitively, the gain at iteration is at least 1/k fraction of the difference between fO U A) and A, in expectation, where A is the partial solution. If ff 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 A may have value smaller than OPT.
To handle this case, it can be shown that the expected value of f(Ou A) satisfies second recurrence:
((((O (a) ( ) + E(
M.)] (1) 1 - F(r(OuAA))))
where M, 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 An = 9). may degrade but is bounded.
Both of these recurrences are solved together to prove the expected ratio of 1 1/e for RANDOMGREEDY: the worst-case evolution of the expected values of f(A)), f(O U A.). according to this analysis,

---

is illustrated in Fig. 1(a). Observe that f(A,) converges to OPT/e (as required for the ratio), and observe that f(o A,) also converges to 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 to obtain a better degradation of [ (O U A,)], 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. Icc).
Stage I: Recurrences when avoiding Z. Suppose Z is an (a, --guidancc set, and that RANDOM- GREEDY selects elements as before, but excluding from the ground set. Then, the recurrences change as follows. The recurrence for the gain becomes:
- (A, FIs ((0 (--)- (A-1)),,
(A-1))
where O \ Z replaces O since we select elements outside of the set Z. For the second recurrence, we can lower bound the term [ (OU Ai-1 1 U M:)] using submodularity and the fact that ZnAi-1 0:
E[SOOA 2 (1- ELT(OUUAAAA)) ( - (E)
1
(2)
Finally, a similar recurrence to (2) also holds for f {())) A.): both are needed for the analysis.
Since Z is a guidance set, by submodularity, f(O') \ 2) 2 f(0)- n Z) 2 (1 a)PPT, which ensures that some gain is available by selection outside of Z. And f(O) f(Ou Z) 2 -1- 3)OPT which means that the degradation recurrences are improved.
The blue line in Figure 1(b) depicts this improved degradation with the size of the partial solution. However, this improvement comes at cost: a smaller increase in E [f (A,)] is obtained over the unguided version. Therefore, to obtain an improved ratio we switch back to the regular behavior of RANDOMGREEDY - intuitively, this shifts the relatively good, earlier behavior of RANDOMGREEDY to later the algorithm.
Stage 2: Switching back to selection from whole ground set. After the switch, the recurrences revert back to the original ones, but with different starting values. Since [ (O U A:)] was significantly enhanced in the first stage, in the final analysis we get an overall improvement over the unguided version. The blue line in Figure ((c) demonstrates the degradation of E [[s (O U A:)] over two stages, while the orange line depicts how the approximation ratio converges to a value 0.385 > 1/e.
The above analysis sketch can be formalized and the resulting recurrences solved: the results stated in the following lemma, which is formally proven in Appendix C.2.1.
Lemma 2.3. With an input size constraint I and ((1 + E)a, -gguidanncee set Z, GUIDE- DRG returns set As with O (kn) queries, s.t. E[f [Ax)] 2 [2 (2-t- +) (1 --) ed e
-(1 + e)a ((1 (1- +) 1)"dd----
a ((1+ e- -2- ))) $(0).
From Lemma 2.3, can directly prove the main result for size constraint.
Proof of Theorem 2.1 under size constraint. Let (f.I) be an instance of SM, with optimal solution set O. If f (Z) 2 (0.385- - f) (O) under size constraint, the approximation ratio holds immediately, Otherwise, by Lemma 2.2, FASTI.S returns a set Z which is an ((1 + e)o, -guidance set, where
a = 0.385 e. By Lemma 2.3,
IC [[ (A+)] 2 [(2- t- e) (1 E)e -1_ (0.385 -0.385 0.615s) ((1 - - -e-
-0.385 =) ((1+ 1-t cl- 1-1-122 -2- =)e - $(0)
(2-
(vk 2 !
1-8 (0.385 - (O)
(1 0.372)
2.3 Deterministic approximation algorithms
In this section, we outline the deterministic algorithms, for size and matroid constraints. The main idea is similar, but replace GUIDEDRG with deterministic subroutine. For simplicity, we
7

---

present 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, INTERPOLATEDD GREEDY, which may be thought of as interpolation between standard greedy [25] and RANDOM- GREEDY [9]. Instead of picking k elements, each randomly chosen from the top & marginal gains, it picks f = O (1/e) sets randomly from O (4) candidates. Although uses only a constant number of rounds, the recurrences for INTERPOLATEDGREIE 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 INTERPOLATHDGREEDI proposed in Chen and Kuhnle [11J) with guided version: GUIDEDIG-S (Alg. 9 in Appendix 1. )) for size constraint, and GUIDEDIG-M (Alg. 8 in Appendix D.1) for matroid constraint. Since only l random choices made, each from O (f) sets, there at most still able to obtain the same approximation factors as in Section 2. The proof of Theorem 2.4 is provided in Appendices D.2 and D.3.
O (co(t) possible solutions, where is constant number depending
Notably,
Theorem 2.4. Let (f. k) be 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 - E) approximation ratio with = 0.559. The query complexity of the algorithm is O (kn(2t-1) where
f 10
92
3 Deterministic Algorithm with Nearly Linear Query Complexity
In this section, we sketch 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. Re- call that Section 2. we described a deterministic algorithm that employed the output of local search to guide the INTERPOLATEDGRREDY algorithm, which obeys similar recurrences to RAN- DOMGREEDY. To produce the candidate sets for each iteration of INTERPOLATEDGREDDYY greedy algorithm (guided iNTERLACEGREEDY) is used. These algorithms can be sped up using descending thresholds technique. This results ThRESHGUIDEDIG (Alg. 12 in Ap- pendix E. which achieves Og (nlog k)) query complexity for the guided part of our algorithm.
However, the local search FASTLS still requires O (kn/e) queries, so we seek find guidance set in a faster way, Recall that, in the definition of guidance set 2, the value f(Z) needs to dominate both f(On Z) and f(OuZ). To achieve this with faster query complexity, we employ run of unguided INTERPOLATEDDGREDDY Consider the recur- rences plotted in Fig. ((a) if the worst-case degradation occurs, then at some point the value of fAA,) becomes close to s(O U A:). On the other hand, if the worst-case degradation does not occur, then approximation fac- tor of INTER ATEDGGREDYY is improved (see Fig. 2). Moreover, we ensure that at every stage, A, contains no elements that contribute negative gain, then will also have fA.) 2 f(O n At).
f(O)
[f(O (
BF(O)
}t(())
E [f(AM]]
0
Figure Depiction of how analysis of INTERPOLAAEDDGREEDD changes if there no (0.377, (..46)-guiidnnc set.
To execute this idea, we run (derandomized, unguided) ENTERPOLATEDGGREDYY and consider all O (E²) inter- mediate solutions. Each one of these is pruned (by which we mean, any element with negative contribution dis- carded 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 value is returned.
8

---

Obeedivee Greesy
1.02
Quertes Greaddy
Objective Greedd
1.00
Queries Greedy
1.01
10f
10a
Fastt GuiidedkGG
Random
0.99
0.90
10
0.98
0.97
10
0.85
10
12
0.4
Number frames solected
Number
selected
kin
(a) Video Summarization,,C1 (b) Video Summarization, (c) Maximum Cut (ER). Maximum Cut (ER),
solution value
queries
solution value
queries
Figure 3: The objective value (higher is better) and the number of queries (log scale, lower better) are normalized by those of STANDARDGREFDY, 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 a 0.377 and 3 = 0.46. That is, if INTERPOLATEDGREEE our algorithm achieves ratio 0.377: otherwise, INTERPOLLATEDGREEDY has ratio least 0.377. We have the following theorem. The algorithms and analysis sketched here are formalized in Appendix E.
produces an (a, -gguidane set, the guided part of
Theorem 3.1. Let kf be an instance of SM, with the optimal solution set O. Algorithm 14
achieves deterministic (0.377 E) approximation ratio with On ( 26 2 262-1) queries,
where 4 10 and l2
Empirical Evaluation
In this section, along with Appendix we implement and empirically evaluate our randomized (0.385 -)aaproxximation algorithm (Alg. 2, FASTLS+GUIDEDRG) on two applications of size- constrained SM, and compare 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.
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-arr 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 E in O (& log(k)nn/)) queries. As our emphasis set
theoretical guarantees above 1/e, least 0.375 in this evaluation. For Lee et al. [21], we set ē = 0.1, which the standard value of the accuracy parameter the literature - running their algorithm with 0.01 produced identical results.
0.01 for algorithm, which yields ratio
Applications and datasets. For instances of SM upon which to evaluate, we chose video summariza- tion and maximum cut (MC). For video summarization, our objective is to select a subset frames from video create summary. As in Banihashem et al. [1].
Determinantal Point Process objective function to select a diverse set of elements [20]. Maximum cut a classical example of non-monotone, submodular objective function. We experiments unweighted Erdōs-Rényi (ER), Barahási-Alhert (BA) and -ttos-Strogatzz (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 independent runs is plotted, and the shaded region represents one standard deviation about the mean.
10000. The mean of 20
Results. As shown in Figure 3 in this section, and Figure 5 and 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
Our code is available at http::/ggtabb.oomnocceyxxxeeeeeg

---

as STANDARDGREEDY, but we improve on Lee et al. [21] typically by at least a factor of 10 and often by more than factor of 100.
Discussion and Limitations
Prior this work, the state-of-the-ar 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 fast local search algorithm to achieve ratios 0.385 and 0.305, respectively, in O (kn/E) queries. The resulting algorithm is practical and empirically outperforms both RANDOMGREEDY and standard greedy in objective value on several applications of SM. However, if & 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 different algorithm: moreover, we speed up the deterministic algorithm to Og (n log k) by obtaining the guidance set in another way. This result is partial answer the limitation the previous paragraph, as we achieve ratio beyond 1/c nearly linear query complexity. However, for all of our deterministic algorithms, there is an exponential dependence on 1/2, which makes these algorithms impractical and mostly of theoretical interest.
References
[1] Banihashem, K., Biabani, L., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., and Monemizadeh, M. (2023). Dynamic non-monotone submodular maximization. Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023.
[2] Bao, W., Hang. J., and Zhang, M. (2022). Submodular feature selection for partial label learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022.
[3] Bilmes, J. A. (2022). Submodularity in machine learning and artificial intelligence. arXiv preprint 222.v:220..00132.
[4] Brualdi, R. A. (1969). Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society. 1(2):161-167.
[5] Buchbinder, N. and Feldman, M. (2018). Deterministic algorithms for submodular maximization problems. ACM Trans. Algoritiuss, 14(3):32:1-322
[6] Buchbinder, N. and Feldman, M. (2019). Constrained submodular maximization via nonsym- metric technique. Math. Oper. Res., 44(3):988-1055.
[7] Buchbinder, N. and Feldman, M. (2023). Constrained submodular maximization via new bounds for dr-submodular functions. arXiv preprint arXiv:2311.01129.
[8] Buchbinder, N., Feldman, M., and Garg, M. (2023). Deterministic (1/2 approximatio for submodular maximization over a matroid. SIAM Comput., 52(4):945-9))
[9] Buchbinder, N., Feldman, M., Naor, J., and Schwartz, R. (2014). Submodular maximization with cardinality constraints. In Proceedings of the Twenty-Fifth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2014.
[10] Buchbinder, N., Feldman, M., and Schwartz, R. (2017). Comparing apples and oranges: Query trade-off in submodular maximization. Math. Oper. Res., 42(2):308
[11] Chen, Y. and Kuhnle, A. (2023). Approximation algorithms for size-constrained non-monotone submodular maximization deterministic linear time. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023.
10

---

[12] Chen, Y. and Kuhnle, A. (2024). Practical and parallelizable algorithms for non-monotone submodular maximization with size constraint. J. Artif. Intell. Res., 79:599-637.
[13] Ene, A. and Nguyen, H. L. (2016). Constrained submodular maximization: Beyond 1/e. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016.
[14] Feige, U., Mirrokni, V. S., and Vondrák, J. (2011). Maximizing non-monotone submodular functions. SIAM J. Comput., 40(4):1133-11533
[15] Feldman, M., Naor, J., and Schwartz, R. (2011). A unified continuous greedy algorithm for submodular maximization. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011.
[16] Gharan, S. O. and Vondrák, J. (2011). Submodular maximization by simulated annealing. In Proceedings of the Twenty-Secome Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011.
[17] Han, K., Cao, Z., Cui, S., and Wu, B. (2020). Deterministic approximation for submodular maximization over a matroid in nearly linear time. In Advances in Neural Information Processing Systems 33; Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020.
[18] Khanna, R., Elenberg, E. R., Dimakis, A. G., Negahban, S. N., and Ghosh, J. (2017). Scalable greedy feature selection via weak submodularity. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017.
[19] Krause, A., Singh, A. P., and Guestrin, C. (2008). Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res., 9:235-288 2844.
[20] Kulesza, A., Taskar, B., al. (2012). Determinantal point processes for machine learning. Foundations and T in Machine Learning, 5(2-3):123-28)
[21] Lee, J., Mirrokni, V. S., Nagarajan, V., and Sviridenko, M. (2009). Non-monotone submodular maximization under matroid and knapsack constraints. In Proceedings of the 41 Annual ACM Symposium on Theory of Computing, STOC 2009.
[22] Liu, Y., Wei, K., Kirchhoff, K., Song, Y., and Bilmes, J. A. (2013). Submodular feature selection for high-dimensional acoustic score spaces. IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2013.
[23] Mirzasoleiman, B., Jegelka, S., and Krause, A. (2018). Streaming non non-monotone submodular maximization: Personalized video summarization on the fly. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI 2018.
[24] Nemhauser, G. L. and Wolsey, L. A. (1978). Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res., 3(3): 177-188.
[25] Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions I. Math. Progrum., 14(1):265-294.
[26] Özcan, G., Moharrer, A., and loannidis, (2021). Submodular maximization via taylor series approximation. In Demeniconi, C. and Davidson. I., editors, Proceedings of the 2021 SIAM International Conference on Data Mining, SDM 2021, Virtual Event, April 29 May 1, 2021, pages 423-431, SIAM.
[27] Powers, T., Bilmes, A., Krout, D. W., and Atlas, L. (2016). Constrained robust submodular sensor selection with applications to multistatic sonar arrays. In /9th International Conference on Information Fusion, FUSION 2016.
[28] Qi, B. (2022). On maximizing sums of non-monotone submodular and linear functions. In 33rd International Symposium on Algorithms and Computation, ISAAC 2022.
[29] Roy (2022). Cooking video. http://wwuukkuuuuuuuuuuoooiiiuua
11

---

[30] Sun, X., Zhang, J., Zhang, S., and Zhang, Z. (2022). Improved deterministic algorithms for non-monotone submodular maximization. Computing and Combinatorics 28th International Conference, COCOON 2022.
[31] Tschiatschek, S., Iyer, R. K., Wei, H., and Bilmes, J. A. (2014). Learning mixtures of submodular functions for image collection summarization. In Advances in Neural Information Processing Systems 27: Annual Conference Neural Information Processing Systems 2014, NeurIPS 2014.
[32] Tukan, M., Mualem, L.,, and Feldman, M. (2024). Practical 0.885-approximmation for submodular maximization subject to a cardinality constraint. arXiv preprini arXiv:2405.13994,
12

---

A Additional Preliminaries
A.1 Constraints
In this paper, our focus lies on two constraints: size constraint and matroid constraint. For size constraint, we define the feasible subsets as [(k) {S C u |S| k}. For matroid constraint, the definition as follows:
Definition A.I. matroid M is a pair (2, 2), where U is the ground set and I is the independent sets with the following properties: (1) 0 Σ: (2) hereditary property: A E I = B E E C A: (3)
exchange property: A, B Z, |A| > [B] = Ez A S. + IIE.
Specifically, we use ((M) to represent the independent sets matroid M. A maximal independent set in I(M) is called basis. Let le be the size of the maximal independent set.
In the following, M' (M',I') ['). We show that SM on M' return the same solution as on M.
consider extended matroid with dummy elements added to the ground set
Lemma A.1. Let M (I, be matroid, and U' = +u E, where E = [(): ....,.... 0 and ej is dummy element for each i E [k]. Let I' = User S, S fcb)...... (c)...... k- }}. Then, M (M'' also a matroid and maxset (S) = maxser f (S).
Firstly, we prove that M = (4', is also matroid by Definiton A.I. Since 0 E I and I S I', it holds that 0 I',
Proof.
Let A' E I' and B= B' LEC S A E I. Since B'nE < A' < k < k - [B,, it holds that B E I' by the
A' E. Then, E I. For every B' S A', since (U, is a matroid,
construction of
Let A', M.B B' I' and A'l > BB Let A= A' E and B = B'\ E. Then, A,B I.
If B'
A
>
BB] by A
Def. A.1, there exists A B s.t. B+x e I. Since (B' +x) \ (B =x) E and
S
B' + E I'. Otherwise, A|| < B), which indicates that |
B B'' Since B'
<
S k
by adding dummy element eg E A' E B' to B', it holds that B' + E
Thus, by Def. A.1, = (') 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 E I, f (S) USU E'), where E' C E. Then, {f(S) S I) (f) S T'}. Further, maxser f (S) maxser (S).
A.2 Technical Lemma
Lemma A.2. (Brualdi [4]) If B, and Bg are finite bases, then there exists bijection B, \ Bg
Bg \ Bj such that Bg + e - (e) a basis for all e E B1 \ B2
Lemma A.3. Let E R-, Xo R. 2 ax;- + for every i E [k),, then
b a1) X 2 h X
1 1 a
Proof. By repeatedly implementing that X; 2 axxi1 + b, we can bound X₂ as follows,
Xx 2 ax +
2 a² X 2- + ab +
k-1
2 Xo +b
Σ
a
1=0
b 611 a
k
13

---

Lemma A.4.
1
1
S log(z) S x 15-1,
Vx > 0
2 e 7
Vr E IR
2 +1
z70-1 0y
Vry S
B Query Complexity Analysis of the Continuous Algorithm in Buchbinder and Feldman [6]
Algorithm 3: Aided Measured Continuous Greedy (J, 1,1,) [6]
input /, solvable down-closed polytope P. set Z E EdI L, (0, /* Initiall
on
Let 81 + i, n and 82 + (1 (1) . Let t + and y(t) 1p
/ Growing (t)
x
while < do
foreach E 21 do Let wr, (t) be an estimate of E [A(2) R(y(t))) [()())((((()) obtained by averaging the values of [(u for r = [48 log(2n) independent samples R(y(t))
end
EnEen wu(() xx(()) Enez (nl)) arg max (Eueu wn(() zt({)} Let ò, be 81 when & < t, and 62 when 2 to Let (t (6)+ 6e) + y(t + 5, (Iu y(t)) xt)
arg max
if E [0,14), if E [t,, 1).
7
Let x(t)
10
Update t + +
11 end
return (11)
In this section, we analyze the query complexity of Aided Measured Continuous Greedy (Alg. 3) proposed by Buchbinder and Feldman [6], which O (n log(n)).
In Alg. 3, queries to the oracle only occur Line 5. For each element in the ground set U r= 48n 6 (2m) queries are made. These queries correspond to independent samples R(y(t))
to estimate E [A[u] (u/ [(y(t)))]. Therefore, there are nr O (n² log(n)) queries for each iteration of the while loop (Line 3-11).
Time variable is increased by 81 te n when t < ts, and is increased by 82 = (1 t.) n when t 2 t.. Thus, there are total of 2n iterations within the while loop. In conclusion, the total number queries made by the algorithm O (n' log(n)).
C Analysis of Randomized Approximation Algorithm, Alg. 2
In this section, we provide a detailed analysis our randomized approximation algorithm and its two components, FASTLS and GUIDEDRG. This section is organized as follows: Appendix C. analyzes the theoretical guarantee of single run of FASTLS (Appendix C.1.1), which is needed to show that it finds 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 1.1.2).
In Appendix C.2, we provide pseudocode and formally prove the results for GUIDEDRG. Specifically, solve the recurrences for both size and matroid constraint.
14

---

Algorithm 4: A fast local search algorithm with query complexity O (kn/E).
Procedure FASTLS (f. ((M) =);
Input: oracle f. matroid constraint (M), an approximation result Zo, accuracy parameter
Initialize: Z f- Zo
/ add dummy elements to Z until |6| = k */ while 3a E Z. E u s.t. a a+c atee e ((M) and A(e A(a a) f
do end return Z
- 7 a+e
C.1 Analysis of FASTLS (Alg.
Pseudocode for FASTLS is provided in Alg. 4.
C.1.1 Finding Good Guidance Set Proofs for Lemma 2.2 of Alg. in Section 2.1
Recall that FASTLS (Alg. 4) takes matroid constraint Z(M) and approximation result Zo as inputs, and outputs a local optimum Z. Here, we restate the theoretical guarantees of FASTLS (Lemma 2.2). Using the conclusions drawn from Lemma 2.2, demonstrate in Corollary C.I that Z is ((1 + =)a, a -guidance set. At the end of this section, we provide the proof for Lemma 2.2.
Lemma 2.2. Let > 0, and let (J,I(M)) be an instance of SM. The input set Zo is an 0g- approximate solution (J. ((M). FASTLS (Alg. 4) returns solution Z with O (kn log(11 /oo)/e) queries such that / (S 7) + f (S Z) < (2 + e) (Z), where S E I(M).
Corollary C.1. Let Z be the solution of FASTLS (f.I(M), If fZ) < aOPT, Z is ((1 + E)a, a) -ggidanee set.
Proof of Corollary C.I. By Lemma 2.2, let S = 0 and S O Z respectively, it holds that f(OuZ)+f < (2+ (10n))<(++))((2))
If f (Z) < aOPT, then
()) < e) f(On2) (1
By Definition 2.1, Z is ()) --giddacce 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 ( 2) - (aa 2 - a) 2 & (Z). By submodularity.
( (Z) (el a) - A (a) a) 2 A (e 2) A(a a) 2 8 (()).
(Z)
K
Hence, the oracle value f(Z) is increased by factor of at least (1 + e/k) after the swap. Therefore,
there are at most [ogg+s//K f(Zo)
f(O) iterations, since otherwise. it would entail f (Z) > f (0),
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 70m log +e/k
(122)
1)
A < n log @
(Z)) 2 af (0); Lemma A.4)
Objective Value. For any S E I(M), we consider adding dummy elements into S until |S] = By Lemma A. I, consider Z and S are bases of matroid M with without dummy elements.
15

---

Then, by Lemma A.2. there exits a bijection S Z - Z \ S such that Z + basis for all e S Z. After the algorithm terminates, for every E Z, it holds that, A(e ( (()) < E (Z). Then,
a(e) is
ef
E A(d
E aEZ
A(a -
Let l 1 =1 - ( (e..,,,))) S = { 0z). By submodularity,
(e1
Σ A(e = (f - ff)) (f
- -() -f (f ( (Z)
2 (f -2) +f 110---af00-10000((222)101111-1-1
- (2))
2
2f + 61 .... (
Also by submodularity,
8
Σ - = Σ
ZZ aa) $ Σ - -
aE2is
1=1
1=1
Thus,
C.1.2 Approximation Ratio achieved by FASTLS
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 2+c approxxmmaaion 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 Zo is an an-approx solution to (f)I(M)). FASTLS (Alg. 4) returns a solution Z such that (Z) > f (0) (2 E) with O (kn log(1 /s) queries.
Proof. By Lemma 2.2, set $ = O, it holds that
(2+ (Z) > ((n
where the last inequality follows by monotonicity and non-negativity.
Non-monotone submodular functions. For the non-monotone problem, repetitions of FASTLS (Alg. 5) yields ratio of 4422- The theoretical guarantees and the corresponding analysis 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.
Algorithm 5: An 1/(4 + 2s) approximation algorithm with O (kn/e)
Input: oracle f, constraint I, an upproximation result Zo. switch point error rate e Zi + U. Z)
/* run FASTLS with ground set U +/
Zg FASTLS Z,,I, Z) /* run FASTLS with ground set U Z1 x/
return 7 < arg max (Z))
Theorem C.2. Let > 0, and let (J.I(M)) be an instance of SM, where is not necessarily monotone. The input set Zo an -p-aproxx solution to ((M). Alg. returns solution 2 such that f (Z) 2 (0) /44 + 2s) with O (kn log(1/ao)/s) queries.
16

---

Proof. By repeated application of Lemma 2.2 for the two calls of FASTLS in Alg. 5, it holds that f (0 u 21) + (on (onz)) < ef+
f ((0 Z 22) + f ((0) Z1) n Z2) < (2+
By summing the above two inequalities, it holds that
(4+ (Z) z (2) (2z)
(()))) +f(() Z1) 22)
2 2[(0)))([(0) ( (OnZ))
(nonnegativity) (submodularity)
2 [(00))+(((0))) (0).
(submodularity)
C.2 Pseudocode of GUIDEDRG (Alg. 6) and its Analysis
Algorithm 6: An algorithm guided by an (a, - set Z with O (kn) queries
Procedure GUIDEDRG (f.I, Z, t):
Input: oracle f. constraint I, guidance set Z, switch point Ao < k dummy elements
/+ Equivalent to an empty set +/
for <- 1 to & do
if i S L k then M; +- arg MC (U)) is basis EeEm A(a|A:-1)
else M, +- arg maX
busis Σ CEE A(alA;-1)
if I represents the size constrainí then + randomly pick an element from Mj
A, A4-1 -0
/* eo is the dummy element */
else if I represents the matroid constraint then
11
0, < a bijection from M, to A;-1, where A;- + x (x) I(M), Vo E M,
e; randomly pick an element from M,
13
A; + A + Eq (:(ee)
14
end
return A₁
In 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, analyze the algorithm under matroid constraints and provide the guarantees and its analysis in Appendix C.2.2.
C.2.1 GUIDEDRG under Size Constraints
In Sec. 2.2, 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 input size constraint I and ((1 + E)a, -gguidance set Z. GUIDE-
DRG returns set A with O (kn) queries, s.t. Els (Ax)] 2 [(2 -t- t) (1 () )
-1
+(1+ ((1 2--=)==----
((1 1-1 c-1 -2-1) 1))=1)) (2-)) f().
We provide the recurrence of f ((O)) \ 2) U A.), ( A₂) and f (A.) in Lemmata C.3 and C.4 and their analysis below to help prove Lemma 2.3 under size constraint.
Lemma C.3. When 0 i t holds that
1 T
E(S((O) 2.)A, 2 1
E ((O)) 2)
E[ (OUA)) 1-
E[F(OUAL))] 1
17

---

When k<is k, it holds that
[( E ( (IF(AL))))
Proof. At iteration i, condition given A,-1 When th, A n Z 0 and M, is selected out of A, Z, so
(OUZ) ((O U U UM) 0 z
((OU))n(O) 4-1 O.
Then.
Elf ((0)2)UA) A-1= Σ E{(()) (((0\))UA-11E32)
(selection of next element)
xEM;
1 I (k: - 1)S (10) 2) / ((0) (
(submodularity)
k (b: 1k- 1)f (10) f( 2) ((OUZUAA- - (OU Z)]
(submodularity)
2 11) (1000
(nonnegativity)
E(S(OAA)) |A-1= = Σ f()))-)
FEM;
1 1b (
(submodularity)
(submodularity)
T
T. [kk - ()0-))((OUUU))+++ (OU2)
(nonnegativity)
When > tk; it holds that
E(S(OUA)) A.) A--1= = 1 Σ ((0
DEM,
2 - 2 (1 (1-1)_(0AA-))
(submodularity)
(nonnegativity)
By unconditioning A;-1, the lemma is proved.
Lemma C.4. When 0 i S t holds that
(A.) - [ [ (A.-))) (E))(()))) E[ (A:-))))
When t. & i<i S k, it holds that
E [f (A.) - E( 2 k
(EI
Proof. Given 1 at iteration i. When i S 1. k holds that
Elf (At) of (A;-1) A = & Σ A
PEM;
T Σ
A(x(A;11)
(Line 5 in Alg, 6)
=EO\(A:
> [f(()))))))))))))))) () (Ai-1)].
(submodularity)
18

---

When i > t- k. it holds that
[A,(A)) (A | Ai-1] - T E
1
(()(A-1) REM,
k Σ (
(Line 6 in Alg. 6)
(/ - (
(submodularity)
By unconditioning A the lemma is proved.
Proof of Lemma 2.3. It follows from Lemma C.3 and the closed form for recurrence provided in Lemma A.3 that
(1- (1- (1- k: 1) $(OU2),
ElS( (0<OO))UAN122001
v0 < i S th
1-10k] f - (1- (1- (1-(1- k ) f F(OUZ)
lek)
E[F(OUANI (1-
1
Vth <isk k
k
(5)
With the above inequalities, we can solve the recursion in Lemma C.4 as follows,
E [f (A(a))
(a)
2
1- (1- x) [tt]]
1
F(0\2))
1 (1
1 k
[tk]
t
(1
1 [ek]
f fOOUZ)
k)
Elf (An)) (6)
2
1 (1-T)
x)
1
[[ (A[uR)] + -t)
1 -
1
k-
8-LAN1-1
[(0)- (00))(11-
-1-(11-
1
1 1:
(0A1)
)(0U0))
k
1
--11-]-1
(11
1
- 11
2 (1 11-1 1)
1 -1T
1 +
R)
1(0)2) 2)
1-1 1. ) (1 (1-1) k)
1) b) k-(kk]
- -(2 (2-1) 1: 1) (1- k)) k-1 )))))²) f(OUZ)
+/
(Inequality (a)
2 (1 - t) (1- [1-1] 1) (1-
kc f + (1111)
1 (2-0)==1
- - -(1-
1
1(0\2)
k
Ko
-(1+111) 1 (1-1)
1 (1-t)k
-(2 1)
1)
(1 (1- k
1 A-1
f(OUZ)
k
(uk- 1 < Like S (k)
(1-1)
1
(1-
1)²² dli - -01 f(0)2)
1 2
2 21--) t) |
c² (-1g(()) +
k
k
(11+ 1 1-t t cl-1_
| 1/
(2 k
e- f(OUZ)
(nonnegativity_Lemmaa A.4)
1
(1-1))
1 1-1 - -0-) ) (((0)-
2 (1 t)
[ (1- k
-' *()) +
k
(1+ 1-t
t
1-1
2
1
k e-1) ((OU2)
(submodularity)
((2-1 :
(1
1
c- c- - 0 ((0) - ((1-1)
11 2 c' c e-1 1(0
(1+ e- -
1
e-) f ((OU))
2-
k
19

---

where Inequality (a) and (b) follow from Inequality 5, Lemma C.4 and A.3.
C.2.2 GUIDEDRG under Matroid Constraints
Algorithm 7: RANDOMGREEDY for Matroid
Procedure RANDOMGREEDY (f.
Input: oracle f. matroid constraint M
Initialize: Ag <- arbitrary basis in I(M)
for < 1 to i do
M; < arg ma a basis Exes 1x)(A;11)
<- a bijection from Mj to 1
24 < a uniformly random element from M;
A - A, 24 (x.)
end return A
10
Discussion about Intuition behind GUIDEDRG under Matroid Constraints. The pseudocode for RANDOMGREEDY under matroid constraints is provided Alg. 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) (EE((A) / (A-11) (EU - 2/ (Ai-1)),
(1 (1-))O0A) ElF + 2 (f A--1 U-)
2) E[ (OU
Fig. 4(a) depicts the worse-case behavior of E Ef (A:)] and Ef A,)]. As discussed in Sec- 4.]bb by selecting elements from outside tion 2.2, we consider improving the degradation of [f A.)
of an (a+ a) ---uiidaecee set Z to enhance the lower bound of [f A U M,). The blue line in Fig. 4(b) illustrated the improvement of [f A.)] with an (a+ + E, at guuidaeee set. However, restricting the selection only to elements outside Z restricts the increase in E [J (A:)) to the difference
between [ʃ ((O) 7) U A;1)) and E (A,-1) This restriction illustrated by the red line in Figure 4(b), indicating degradation in [(O(( \ 2) U A.)-
To benefit from the improved degradation of [f (OU A:)], we consider transitioning selecting elements from the whole ground set at a suitable point. The blue line in Fig. 4(b) illustrates how [f (O U A,) degrades before and after we switch, and the orange line illustrates the evolution of Eff (A,)). Even starting with an inferior selection at the first stage, we still get an overall improvement on the objective value.
We provide the updated recursions for f ((0) U / A,) and f (A;) in Lemma C.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.
Lemma C.5. When 0 í t. it holds that
2
E[f((O) ( U AI)
((O(O))UAAL))) -1)
E[S(OUA))] 2 (1- ElS(OUA + 100)
2
When t. <<i k, it holds that
() (1- E [IF(OUA-)))++
20

---

f(O)
(00)
(O)
[[((O
[RO u
Elf(o u uA
F(0N2)
F(012)
E ZZ) uA)]
1(0)
1())
(1)
$ [F(AI)
[(F(A)]
0
k
Figure 4:
This set of figures indicates how guiding benefits RANDOMGREEDY under matroid constraints. The figure (a) depicts the evolution of (OU A:) and (A:) with RANDOMGREEDY.
The figure (b) illustrates how the degradation of f (O U A;) changes as we introduce an (0.305 - e, -0305))-giddance set. Additionally, which is the value that the solution approaches with the guidance. The figure (c) shows the updated degradation with 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; decreases initially when the selection starts outside of Z, benefits from the improved degradation of f (O U A,) upon switching back to the original algorithm.
also need consider the degradation of [(O Z) A.),
Proof. When i < (k, holds that E[f [[O 2) U JA) A--1 = Σ ((002))((4112=-0(t))) h
ZEM;
1 Σ (O \ 2) UA-1) + ((0) (A
(submodularity)
k
ZEM,
1 [f ((0) Z)U
(10) +) + 1)ʃ ((0) Z) U + Z)]
k
(submodularity)
2 h
[ik 2)) ((0) 4-) 3) ((UU))
(submodularity; nonnegativity)
EQU A.) A--1= = Σ
1
Σ [A(OUA==)++ (x)))
(submodularity)
h
ZEM,
1
A. M.) (OU - (submodularity; nonnegativity)
(submodularity)
1.
1
When i > tks it holds that
E (OU 42) A--]= = Σ ((0U(A-1==-000))
ZEM,
1 (A
(submodularity)
h
#EM,
1 (ou - - (0000AA)))) + (k- 10 1,1)) (submodularity)
1
(1= A [
(nonnegativity)
By unconditioning At-1, the lemma is proved.
21

---

Lemma C.6. When 0 <i t k, it holds that
[ [ (A-11)) 1 (EO A.-)] - [f (Ai-1)))-
When t. < k, it holds that
E (A.) (f [Elf (OJ (.-1) - (2 (A,-1))).
k
Proof. Given A,- at iteration i. When i S t k. since O is a base, 0 (A,-1 U Z) with dummy elements is also base. holds that
El (A.)- - (Ai-1) A
Σ (2
(A:-1))
K:
xEM,
Σ [x) oz(x)) (Ai-1))
(submodularity)
zEM,
Σ A(x|A-1)+ + Σ ( (Ai-i))
(Line in Alg. 6)
(E0
ZEM,
IV
| A / (Ai-1).
(submodularity)
When i> > t- k. it holds that
E(f (AA-))
Σ (A (A,-1))
xEM;
Σ AA( +f ax())) - (A1-1))
(submodularity)
M
Σ #EO
(x|A,11)
1 Σ
- (A-1))
(Line 6 in Alg. 6)
k
seM;
1 (A,-i)
()(OUA,))) - (A,11) (A
(submodularity)
Lemma C.7. With an input matroid constraint I and a ((1 + e) -gguidanee
set 7, GUIDEDRG returns set Aş with O (km) queries, s.l. [ (Ax) >
1 2
+ (3 - t- 1) (1 2) 2(t - e - (1+ ((1 2)² 2(t-1)) -22)
() + 1 ( (3 - +) 2)) 10).
Proof. It follows from Lemma C.5 and the closed form for a recurrence provided in Lemma A.3 that
2) 2 - ( 2)
)) ((OUZ) Z),
E[f((0) A.) 2 f
AA < S tk:
k
(11 1 k
8- [ck]
- -(1- 2
(1-2))
[[U(O
1+
f(0) 2
fOU f(OUZ))
f
Vtk <isk
2
k
k
(6)
Then, by sovling the recursion in Lemma C.6 with the above inequalities, it holds that
(a)
2
[ 5(0) 2) -
(
[ck]
L
2
[tkj-1
[ (A
2
1 - 1
1
f (OUu)
2
k
4 4 k:
2
k
(6)
2
k [tk]
1
(
2
k- (ekkek-
[ff (Ax)
2
1
k
[f (A (A()))
+
2
2
+
2 -
t + k
k
f(0)
22

---

1 - t
2 /:
[ta -1
- (1-7)
2
k-1
1
f f(OUZ)
2
k)
2
k- [-lkk]
- (1
-
2 h
S 10) (10 +
1
2
1 -1+
11 1)) (1
2 k-(ck]
110)
1:
k
(6
+
1 1-1 1.
(1
2
k- L1ke
(3 1)
(1 (1-3)
2
)
f 5(OU2)
2
1
2 k
k
(Inequality (a))
2
(1-1)4+1
(1 - k
2) k)
1 +
1 - t 1)) (1 (1-
2 (1-1)k)
1(0) +)+
S(0)
2
k:
2
2
k
1 [1
+ - (1
2 (1-1)k
3
1)
(1- 2
f )
k-1
f(OUZ)
2
k:
2
k)
(1k (11-10 1 <[ik] S (kk
2) (211-11 -E-2 ((0)2)+ 2)++
(1
1
- 1+ tt)
(1-
2 -
E 2 S10)
(2 2
k:
2 + 1 1-t
(2 11 c f [(OU))
3
1 1- c (21-1)
(nomnegatiiityLLemmaa A.4)
2 k k
1
1
3
- 111 (1
2
2(1-1) 1) - =²) 510) ( (1
2
2((--1)
1) - f f(Onz)
+
2
2
2
k
1
1 1 t
2 1)
3
1/
k: e e-2
1
.[ou2)
(submodularity)
2
where Inequality (a) and (b) follow from Incquality 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 so- lution set O. If f (Z) > (0.305 - e) (O) under matroid constraint, the approximation ratio holds
immediately. Otherwise, by Corollary C.I, FASTLS returns a set Z which is an ((1+e)a, (1+e)aaaa-guuidnee)
set, where 0.305 8.
By Lemma C.7 and Z is an ((1 + E)o, a)) -ggiiannc set with a 0.305 E,
E (Aa))
2
1
1
+
3
- 1- 8 (1 - -2))(2((11)
e -2 - (0.305 - 0.695e) (11 (1-2s)² 2 - -2)
2
2
2
(2
1-1
3 - 8 -2 } f (0)
- (0.305 - =)
+ 1- 1-
(2(1-1)
(Vk: 2 )
2
2 (0.305- -) (O).
(t = 0.559)
D Analysis of Deterministic Approximation Algorithm
In this section, we present the pseudocode of deterministic algorithm and its analysis. The organization of this section is as follows: firstly, in Appendix D.1, we introduce the deterministic subroutine, GUIDEDIG-S and GUIDEDIG-M, along with their analysis: then, in Appendix D.2, we provide a randomized version of the deterministic algorithm for analytical purposes; finally, in Appendix D.3, we provide the deterministic algorithm and its theoretical guarantee.
D.1 Deterministic Subroutines- GUIDEDIG-S and GUIDEDIG-M
Inspired by INTERIACCGRREED algorithm, a subroutine of INTERPOLLATEDGREERDY, proposed by Chen and Kuhnle [11], we introduce guided versions of it for both size and matroid constraints.
23

---

Algorithm 8: A guided INTERLACEGREEDY subroutine for matroid constraints.
Procedure GUIDEDIG-M (J, (J, G,
Input: oracle f, matroid constraint M, guidance set Z, starting set G, set size l Initialize: A, A 0
for i 4- 1 to k do
X; + {- E (GUAUD Z): A ar arg jEl A(2
A A + aj As; A;; +
end
a bijection from G to s.t. (GUA)) \ (EreA, (x)) is a basis
return {(GUA)) o :1sis}
10
The algorithm for the size constraint closely resembles INTERLACEGREEDY in Chen and Kuhnle [11]. Hence, we provide the pseudocode (Alg. 9), guarantees, and analysis Appendix D.I.I. 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. More- over, 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, INTERPOL ATEDGREEDY [11] constructs the solution with l iterations, where each iteration involves calling the INTERLACEGREEDY subroutine and adding k/l 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 l solution sets, where each addition dominates the gain of distinct element in O; 2) by exchange property, establish 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 E(e + 1) to f. We provide the theoretical guarantees and the detailed analysis below.
Lemma D.I. Let O I(M), and suppose GUIDEDIG-M(Alg 8) is called with (f. Z, G, where Z NG- = O. Then GUIDEDIG- M outputs candidate sets with O (Ekn) queries. Moreover, a randomly selected set G' from the output satisfies that:
DE(((')) 2 (1-7) 2
( (1- :) 1(002))GG)
(G)) E+1
2) E)E[(OU)))) (1-7) (OUG)+ 1 (100=++0000
3) ((O /2 2) 2 (1-?) f((O) X U)))+ 1 (()))))))())))))2())))))))))))))
. } } be the sequence with the order of clements being added. Since A and O Z are basis of M (by adding dummy elements into O 2),), we can order O 2 {01, .. og} o.} is an independent set. Thus, o, E X,. Let A! be A, after s.f. for any 1 < i i k, fai..... a; 1.-1 i-th iteration. Therefore, for any S s by submodularity,
Proof. A= {af, az... ......,
A(o,GGAA,) < (aIIGAA!-") <AQOIGUA
+ # {((O)))jGUAA))/(CUA S > A(AGGUAA) Σ (aGGGGUA =
By summing up the above inequality with 1 1sisc.
(e+ 1) A(AIG) > Σ
((O))))GUA))4FF
j=1
24

---

2 (e- 1). (()-
2 ((0) -G)
(nonnegativity)
Then, can prove the first inequality as follows,
([(())-(G)] - Σ (A)UA)
1=1
1
Σ A/ - ((G)
7
(1- 1
; / /(10) 2)) {+1 1+1 [(G] 1
2 ++1
E[f())) 2 (1- 2
f(G) + हमं (1-H) f (10 2))
1
8
By submodularity, nonnegativity, and Z n A = 0. the last two inequalities can be proved as follows,
[lf(O)])) = 1 - Σ ((
2 Σ [XA4:00)++((((()=-144111
(OU))) (UOUGUA--10000(0-100000--000
2 (1- ((QU=)=(10--00002)))))11011
1 / Σ (10) ((012)((()=(4))A3)
2 1441000220001+001100000111101110
8 (UUGAA)-KK01//000)(((11111- ()))) 22))
1 (1-2) 2) f((()) 2)G) + 110 Z) ((0 -f(Unn)))
D.1.1 GUIDEDIG-S and its Analysis
In this section, we provide the pseudocode, guarantees and analysis of GUIDEDIG-S, which highly resembles ENTERLACEGREEDy in Chen and Kuhnle [11].
Lemma D.2. Let O C 21 be any set of size most k, and suppose GUIDEDIG-S(AIg 9) is called with (f, k; Z, G. f). Then GUIDEDIG-S outputs f(E + 1) candidate sets with O (fkn) queries. Moreover, with probability of (f + 1)-1, a randomly selected set A from the output satisfies that:
1
D) (4)) 2 Elf ((0 \ Z)] + 1+1 (G):
8
[) N (1-2) (-=) (F(0u(22))=
3) E) ((0) \2) (1-)) (
25

---

Algorithm 9: A -appoooiooinn that interlaces & greedy procedures together and uses only 1/6 fraction of the budget.
Procedure GUIDEDIG-S (f, Z, G,
2
Input: oracle f. constraint k. guidance set Z, starting set G, set size l
{ai...., [t) + top elements in u () with respect to marginal gains on for u + 0 to in parallel do
if u 0 then
Au, G U [ar), for all 1 < l
else
Au,1 t GU [aw). for any 1 <
end
10
for j x- 1 10 k/L - do
11
for f- 1 110 do
J arg max ( A())Au.))
Au,i Au,i U {1ga}
14
end end
15
16
end
17
return : 1
Proof. Let Omax = arg ((Uz)) Aoo|G), and let (ai...., az) be the largest elements of (A(x]G) : x Eu E (G) as chosen on Line 3. We consider the following two cases.
0z} = 0. Then, Omax & {aI..... } which implies that A(au G) 2 (oo|G), for every S u S l and o O (G U Z); and, after the first iteration of the for loop on Line 10 of Alg. 9, none of the elements in O (GU Z) is added into any of {Ao,:) We will analyze the iteration of the for loop on Line with u = O.
Case (0) (
Since none of the elements in O \ (GU Z) is added into the collection when j = 0, we order O (G U Z) (2,,02,...) ...) such that the first & elements are not selected in any set before we get to j = 1, the next l elements are not selected in any set before get = 2, and on. Let {1....,(} l}. Let Ab,i be the value of Ao,; after j elements added into it, and define
Ao, = A the final value. Finally, denote by 6, the value (2),alAb.)) Then,
f {(00) (00 f (Aor))
Σ
A(olAo,))
(submodularity)
2)
Σ
A(olAo.))
(G C Ao,i)
OEO)(GUZZ
2
(00144.,) + Σ A(o1(4).) +...
(submodularity)
t=1
(=t+1
k/E
Σ 8, e(f (Ao.)) - (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 & f, it holds that,
1 8 (Ao.)) 2 7
E [((A))
S((O) Z)U Aos) + 2+1 J(G)
+1)
5+1 / (G),
-
26

---

Since Ao. A G for any S #1 S l, and each 21,4 is selected outside of Z, by repeated application of submodularity, it can be shown that
1 Σ S(1O) (10)2)) Ao.) Ao.)
E (10 2) () 1)] A
((0) Z) + / (10) Z)u (U
2 7) f((0)) (00
[[S(OUA)] A 1 Σ (OU Ao.)) (1- 2 (O
2 -
Therefore, if we select random set from (Ao.: :1 sis f). the three inequalities in the Lemma hold and we have probability 1/(e+ + 1) of this happening.
Case (O) \ (G U Z)) fai,..., dx) * 0. Then Omax E {al,.... Oz J. a, Omnx, for some C. We analyze the iteration u of the for loop on Line 4. Similar to the previous case, let i E {I....,{}. define A be the value of Au,; after we add j elements into it, and we will use An,
E I,,..
for k/t u,5. Also, let 5, A (23s1A4,7"). Finally, let 21,; au and observe A = GUU {au). for any i E EJ.
Then, we can order \ = (01, 02
02, ...... such that: 1) for the first elements for max (G) 51; 2) the next é clements {o1)2=0+1 are not selected by any set before we get to j which implies that A (oi AM,,) S 82, and so on. Therefore, analagous to the the previous case, we have that
foi A(o G) S
1
Elf N E+1 Els ((0 (U))
A]]+ + e+ (G)
Since, Au,i, 7 Auu., GU } for any 1 i # i2 S l, au E O \ Z, and each 2₁, is selected outside of Z. by submodularity and nonnegativity of f. it holds that
1 8
Elf ((0) \ Z)U
f((0) \Z)
2 2 S((O) Z)UG) + 1 (10) Z) 2)
1)
S((0) Z)U (1 (01))) ((0)
[[((OUA)] & Σ ((OUAA))) (1- 1=1
2 (1-)) S(OUG)+ 1 ( (((00(Z()))((003))
Therefore, if we select random set from {Aa,: 1 S i S E), the three inequalities in the lemma holds, and this happens with probability 1)-1.
D.2 Randomized Version of our Deterministic Algorithm
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.
27

---

Algorithm 10: The randomized algorithm suitable for derandomization.
Input: oracle f, constraint Z, an approximation result Zo. switch point I, error rate 8 Z. < FASTL.S(J, &)
Initialize L f 9 Ag t-8 0
if I is size constrain! then
for <- to do i te then A; + random set in GUIDEDIG-S(f.I,2 A1-11 elseA; + a random set in GUIDEDIG-S(fII.0.. A..1.)
end
else
10
for i 4- 1 to do
11
i S tf then A, < random set in GUIDEDIG-M(.III22AA... else A; t a random set in GUIDEDIG-M(f.Z A,-1,)
12
13
end
14 end
return + arg max ((2)
Theorem D.3. Let (f,I) be an instance of SM, with the optimal solution set O. Algorithm 10 achieves expected (0.385 - 5) approximation ratio with (e (8+1)) 1)- success probability and input I = 0.372 under size constraint, where e = ge. Moreover, it achieves an expected (0.305 - s) approximation ratio with 0.559 under matroid constraint. The query complexity of the algorithm is O (kn/E).
10
D.2.1 Size constraints
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 of the for loop in Alg. 10, the following inequalities hold with a probability of (e + 1)-
(A,) 2 e+1
F [f
+
1
[10)) 2)
(1- ( 110u2).
isisu
e+1
1
1)
6-14)
f(0) (1- ( 1 (1- [1e]
S(OUZ)
E[f (A)) t+1 Ef + t+1
1
te<ise
8
Proof of approximation ratio. f2) 2 (0.385 - f) (O), the approximation ratio holds immedi- ately. So, analyze the case (Z) < (0.385 8) (0) in the following.
Recall Corollary C.1 that Z is a (1 + s)a, -uiidance set, holds that ( (0.77 - 1.615s) (O) and f (0 n Z) < (0.385 0.615e) (O).
By repeatedly implementing Lemma A.3 with the recursion in Corollary D.I. it holds that
[d]]
[ (1 (1- 1) [*]
E [f (A[a))] 2 1 11- (1-(--
- [+1 (F(0\2)- +
1
f(OuZ)
E+1
2 1 -- - 8 1 ( ) (000)-((022)-00122 +
[18] (1 (1- 11) [+]]
f(ouz)
e+l
(submodularity)
E(s (Ac)) 2
1 1-111
[-1M)
E [ + l [1]
(1-
1 [-1w]
(((0) - (1 (1- (1 (1-
2) (0])
f(OUz)
2=1
e+1
(1-2111
1
(1-1)6+1
(11 -100))000)))
(+1
28

---

tl 1 1+3 1
1 (1-1)6+1
1 (1-2) S(OUZ)
1 1
1+1
+(1- t) (1
(1-2+1) )
1
(1
(1-2)
1
1 (1-1)6+1
(100) ((1))-11(()) (1-(1-2) (6-1)
S(OU2)
e+1]
((- (1- 1
(te-1< [[t_
-
(1--+1)
1
(1-t)e
1+ (1+2) 1) (1 (1-2+1)
1 441
)(7)
(((UZ))
1-1
(1 1- e+1) )
1
(1- (1- (1-et1)
1 (1-1))
11 1 1) tt-1
f(OuZ)
e+1
2
((--)) (1-2) (1-1)6-1
+(1- 1) (1- e e+1)
1
f(0)
-(1-2) (1-1)e
2) (1- -)- 1
1)
1 4
f(OUZ)- -
0 )-))))))))))
(OU 2)) +t ( (1-1) 8) (')((OU))
3
+ (1-t) +(--t) 1) (1 (1-1)² (1-1)==1000-=000002++ + (1()o=)())z))
((0))-((02)=(((12))) 0; nomeegativity Lemma A.4)
2 |de - + ()) ((0) ()c"))))11---- -c +
(f( Z))
- -106 - (1-1)e--1 (1110))
(Let== 1 :66 -
2 - -1)+ -000-)))))
- 1) + 1)e² - (c + 1) (0.77- - 1 (0)
-00=- 0.615e) (0)
(1000)=11002)<<(77-11116 (0); f (0 n 2 < (0.385- - / (O))
2 6)
(0 < < 0.385; = 0.372)
D.2.2 Matroid Constraints
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 of the for loop in Alg. 10, the following inequalities hold,
E(S 2 (1-
2
E (A(-i))
8
1
1 (1-)
(f(O Z) -100)2)-22
1 ( (1-
è) 2)
41) f F(OUZ)) ,15iste
1
E+1
2
(1 (1-2)
2) 8
Eff
Elf (A(-))]
( 1-
à)
1
( 1
111
1
(1-2)
2) (1-2)-))
2 1-10
f(0) 2 (1122) 6-tl
(1- (1--))---11 -
2
(1=)))((ou)) tt desise
e+1
2
Proof of approximation ratio. If (Z) 2 (0.305 - (O), the approximation ratio holds immedi- ately. So, we analyze the case (()) < (0.305 / (0) in the following.
Recall that Z is (1 + E)a, a) -uiddance set in Corollary C. holds that [( (0.61 - ff (O) and f (0 n Z) < (0.305 0.695z) f (0).
29

---

By repeatedly implementing Lemma A.3 with the recursion in Corollary D.2, it holds that
8-1
(1 (1-(1-9) (1002)-1((022)) + +1 (1112 2) |
"
[ (A(a)) 2 2(
8)
S(OUZ)
1-1
[1-((1-2) (1-2))() (110)-11022)-11
1
(1 2)
|6||-1
2
+t
5(OUZ)
2((+1) + 1)
i
(submodularity)
2)
[-lee)
E E(F(A())) + e-1
[
1
1 ++ 1) (1
1
2
2 6-1461-1
Elf [Aa)) 2
(1-
2+
S(0)
2((++)
2
2
1
-(1- 1)
(11-3
2
6-100-1 - -(1-2)
2) 6-1
Souu)
8
8-1
11 +
3
-t - ---11 -)))) 1
(1-1) 2) 11-))-²
2) 1-11
- (1-2) 110)
2
2( 11) 1)
2 (2
(1-
2) (1-1)e
- (1-2) f(0nz)
2
) (1-2) 2) 1-t1
-
(3
- (1 (1))))1)
1 1(OUZ)
2
(1l [[]]] S 10
1-2
(1]
3
-- 1) (1 (1-2 2
2(-11) - f(0)- -00) (20-0))(111
2 (1-2)0²) ) f f(nzz)
+
2
2
8
1-1
3 1
2 1 )2) ((2U0)
21-11)
(Lemma A.4; nonnegativity)
2
7
1-1
(6
3
1 1)
(1 (1-7 ((111) - - (10) - (10)- ((=
2
-1) ))---(2-1) 2 ()-1)=20-11) s(onz)
c- 1)
1
+1)
2
(( (6-+1-1
1-t
(3 1 i 3 x22 (((002++((022)))
2( 2(1-1) 1)
1-7
2(e + 1]
6-1
[
[2 +
2 -
- -1-1 1) (1 (1-2)
2
e
(111))
1) - -2 -00.30 - 0.695e)
((
1
e
- -2_ 11
_
(1 -1) ((0-1))
-(0.61 - 1.695c)
(6+
1-
+ 1-t t
(1--1)
3 1
e 2
1 (
2
8
> (0.305- - (0)
(e
10.
0
<<< 0.305; L = 0.559)
92
D.3
Derandomize Alg. 10 in Section 2.3
In 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 - s) approximation ratio with L = 0.372, and a deterministic (0.305 - s) approximation ratio with t = 0.559. The query complexity of the algorithm is O (kn(?--1) where
10
9
E Proofs for Nearly Linear Time Deterministic Algorithm in Section 3
In this section, we provide the pseudocode and additional analysis of our nearly linear time determin- istic algorithm introduced in Section 3. We organize this section as follows: in Appendix E. we
30

---

Algorithm 11: Deterministic combinatorial approximation algorithm with the same ratio as
Alg.
Input: oracle f, constraint I, an approximation result Zo. switch point i, enror rate g 2 + FASTLS(F, Zo. E)
3 Initialize l + 9e GD < {0}
I is a size constraint then
for 2 1 to do
G;
for A;-1 E G do
i s tf then
G; G, GUIDEDIG-SSf.A222A--1
10
else
G; G. GUIDEDIG-S( A:-1;
12
end
13
end
14
end
else
16
for i 6- 1 10 do
17
G; g 0
18
for A,-1 E G do
19
i tl then
20
G + G; U GUIDEDIG-M(J,K -
21
else
22
G. + G, GU
23
end
24
end
end
26
end
27
return A" + a (Z), A GG)
provide speedup version of GUIDEDIG-S which queries O (og()) times; in Appendix E.2, analyze the subroutine, PRUNE; at last, in Appendix E.3, we provide the pseudocode of nearly linear time deterministic algorithm and its analysis.
E.1 GUIDEDIG-S Speedup
In this section, we provide the algorithm THRESHGIUDDEDII, which combines the guiding and descending threshold greedy techniques with INTERLACEGREEDY [11].
Lemma E.1. Let O C U be any set of size at most k. and suppose THRESHGUIDEDIIGAAA 12) called with (f, k, Z, G). Then THRESHGUIDEDIG outputs E(E + 1) candidate sets with O (En log queries. Moreover, with probability (E + 1)-1, a randomly selected set A from the output satisfies that:
(i-- +1 ESS +E)++EES(AAA ( -
E
L (G)-
1)
2) E [](OUA)]] (1 (1- ((OUU))++ (00((2)))) ((OU)))
3) [[ ((0 Z)) 2 (1-2) ((0)) + fu ((0)))))
Proof. Let Omas arg max.coorxaau A()|G), and let (a....,, a²) be the largest elements of (A(x(G) & E E \ (GU (GUZ)), chosen Line 13. We consider the following
cases.
Case (0) \ (GUZ))n (a),... a+} 0. Then, Omax & (aI,..., ag) which implies that A(a,, G) > A G)) for every 1 < < l and O (GU Z); and, after the first iteration of the while loop
31

---

Algorithm 12: A guided INTERLACEGREEDY subroutine with descending threshold technique for size constraints.
Procedure THRESHGUIDEDIG (f. E)
Input: oracle f. constraint k. guidance set Z, starting set G. set size L, eπrrr e > 0
{ai...., .t] + top elements in 4 (G Z) with respect marginal gains on G
for u < 0 to in parallel do
if a 0 then
M < ((a+(G)
Au, + GU {ar), for any [[]
else
M + A(au
10
Au,1 G U {au). for any / [4]
end
12
- M, + true, for any / E [$]
13
while
v 1 do
14
for e 1 to l do
15
if 7 then
V + u \ (Ufzz Aut 22
16
Au,i, ADD(J, V, E, Ti, M
if [Au, \ \G| k/L V T,
eM
then I false
end
20
end
21
end
22
Gm f Gm U (An, ..., A
end
24
return S* +- arg max (S()) Sz E Gt} ( Procedure ADD (f, A, Tmin):
25
26
Input: oracle f. candidate set V, solution set A, threshold т, and its lower bound Tmin
27
while T 2 Tiin do
28
for x E V do
29
A x
A) 2 then return A < AU fz),
- - =)T
31
end
32
end
33
return A, r
Line 13, none of the elements in O (GU Z) is added into any (Aa,)i We will analyze the iteration of the for loop Line 4 with 0.
For any [e], let A be Ao,1 after we add j elements into it, 7(1) be 7. when we adopt j-th elements into Ao.i, and 7(1) M. By Line holds that A GU {ar}. Since (0 \ (GUZ)) {aI...., a = 0, and we add elements to each set in turn, we can order 0 (GUZ) = for, 02 o2. such that the first é elements are not selected by any set before we get (1) the next & elements
not selected in any set before get A and so Therefore, for any j < |Ao Gl and lj. o; filtered by An, with threshold , e), which follows that A ((.14407) (5) (1)
((j 1)-1)+1
((4 ()((1))1111)))))))))) ; for any Al ( <i< (QV()))), which follows that ((o;(Ao.) &M/k. Thus,
0 are filtered out by Ao, with threshold eM b
f {(0) (2) Ao,) (Avi) S
Σ A(o)Ao.))
(submodularity)
AE
< Σ A(olAo.)
(G C Ao.)
(EO\(GUZ)
32

---

26
5 Σ
A (0.14
+ Σ A )
+ +.... E s>tlAb./io]
A(oi|Ao,)
(submodularity)
1=1
i=t+1
S e. f (Ao.1) - - +&M
1 1
Le. f -A (0)
1-6
By summing up the above incquality with all 1 S ( it holds that
6 ( 11- +1 (i)EES(A) (-=+1)E(((A) 2E ((0 U)
i -G))
(8)
Since Aud, n Auil = for any 1 1 4 + 12 < holds that ((0) 2) U Au,,)) n ((O) U (0 (0\ G. By repeated application of submodularity, it holds that
1 = - - S(10) ((O)2)) 2
[[ -
2 - 1
S((0) 2)) + + ((0) Z) (UL))Ao))
8)
u) u (0o
2 1 (1-7)
E[[(OUA]] 1 - Σ S Ao,) (1- r (oU +
2 (1-2) (
Therefore, the last two inequalities in the theorem hold.
Case (O (GU u Z)) n {aI...., ae) + 0. Then Omax E (aI....,at} at)- Suppose that a, Omax- We analyze that lemma holds with sets {fu,
Similar to the analysis of the previous case, let A be Ag, after we add j elements into it, T) be n when we adopt j-th elements into Ao, and 7/ = M. By Line 10, it holds that A G {a..) Then, we can order O \ (G (GUZ Z U faw)) = for, . such that the first elements are not selected by any set before we get C the next elements are not selected any set before we get (1 and so on. Therefore, Inequality 8 also holds in this case, where A is a random set from {Au,)
Since, Og O, and And, O Au,2 G U {aw} for any 1 I l + 12 l, it holds that (()) Z) U An.s,) n ((0) 2) Am,,,, = O U G. Following the proof of case (0 (GU Z)) n {ai,..., az) } = V. the last two inequalities still hold in this case.
Overall, since either one of the above cases happens, the theorem holds.
E.2 Pruning Subroutine
PRUNE is used in Alg. 14 to help construct the (a, -ggiddnnc set, where 0.377 and B 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 E A and its related output set A' E A', it holds that,
(A')
2) f (S 2
3) (T) (A') A'.
33

---

Algorithm 13: A pruning algorithm which deletes element with negative marginal gain
Procedure PRUNE (f,
Input: oracle f. sequence of subsets A
Initialize: A' 4-
for A A do
for x E A do if A [z|AA - z) 0 then A f- A
end
A' + A' {A}
end return A'
10
Proof. Let A; be A after we delete i-th element 2;, An be the input set A, Am be the output set A'. Since any element x; being deleted follows that A (rr,)A A:) < O, it holds that f (A,) > I (A; + xz)
I (A;-1). Therefore, f (A') (Am) > > / (An) = f (A). The first inequality holds.
For any 24 E A \ A', it holds that ( A,) < 0. By submodularity,
( Σ
S
A (x) <
The second inequality holds.
For any y E A' \ T, since is not deleted, there exists 0 S iv S m such that A AvlAAr,) 2 0. By submodularity,
f(A)
E
A(vAA) Σ A(vlA,,) 20.
BEANT
WEANN
The third inequality holds.
E.3 Proofs for Theorem 3.1 of Alg, 14
Prior delving into the proof Theorem 1, we provide the following corollary first. It demonstrates the progression of the intermediate solution of THRESHGUIDEDIG, after the pruning process, relying on Lemma E.2 and E.
Corollary E.1. Let O C u be any set of size most k. Then PRUNE(TTRESHGUIDDDIGG.. kf, G, outputs E(l + 1) candidate sets with O (en (og queries. Moreover, with a probability of (e + 1)-1, a randomly selected set A from the output satisfies that:
1) (1==+))(1((A)) (1-
+OUG)+ L -
2) E(f(OUA) 11 (1 f(OUG):
3) f(o n < f(A).
Theorem 3.1. Let kf, be an instance of SM, with the optimal solution set O. Algorithm 14 achieves deterministic (0.377 E) approximation ratio with On 26, gg 26, queries, where 4 and lg
Proof. Following the proof of Theorem 3.1, we consider two cases of the algorithm.
Case 1. For every A Z, holds that (OUA) 2 (.4) Then, prove that maxcez (C) 2 (0.377 - f
In the following, we prove the theorem by analyzing the random case of the algorithm, where randomly select a set from the output of PRUNE (THRESHGUIDEDIIG, Suppose that we successfullly select set where the inequalities in Corollary E. hold. Let A, and A be random sets in Z,
34

---

Algorithm 14: Nearly linear-time deterministic algorithm for size constraint
Input: oracle f, size constraint k; error rate
5 2 Initialize 2, +- 3 l2 - _ 1 f 0.3
3 D Create guided sets
7o f 0
5 for i 4-111
to g do
Zi +-
7
for A,-1
E 11-1 do
Z; + Z, U URINEETTRRSSSGGGDDDDGGG A.,,
end
10 end
11 Z + -U
12 b Build solution based on guided sets
13 G++ 9
14 for AA Z do
15
Go + 0
16
for i to fg do
17
G, + 0
18
for
B E G do
19
i < tf then
20
G; + TUITESSSGGGG
11-1,,,,5")
21
else
G, + G, U THRESHGUIDEDIGGff k. k, B, E2
22
23
end
24
end
25
end
26
G GUGL
end
28
return C +- arg maxcezuG ((C)
and Z,-1, respectively. Let (1-1) 11 4'-1 0.46 2 (1 1. )))² Then, by Inequality (2) in
Corollary E.I, when i < <<,, [ 2 (1 1 2) f(O); when i 2 1", f(OUA)) 2 0.46.(O)
by assumption. By applying Inequality (1) in Corollary E.I,
1
1
1())
I-ee
41-1"
61-5"
E(f (AG))2
(A;(): +
1 -
1
- 64)--0)((O)
b I-g-
+1
E
+
1
I-g7
81-8"
1
1
1
1- 2,
11-
0.46
b
+1
1
E
E1
+1
41
1
1
1
f(0)
f1
+1 1
1-
log(0.46)
1
0.46 E' (1 (1-o22te)
1
c-
+
1
f(0)
- + 1
log
11
E
0.46
1
- +1
(Lemma A.4;
(1
0.46 >
(1 11)))")
35

---

2 (0.377- - =))
(61 5 = 200<
3
< < 0.377)
Since we return the best solution in Z and G, it holds that f(C*) 2 [ (Aa))) 2 (0.377 - e))(
Case 2. There exists A E Z, such that f(OUA) < (.46f(0). Then, we prove that maxcec f (C) 2
(0.377 =f), (0).
Suppose that f(A) < 0.377f(O). Otherwise, f(C*) 2 0.377.(O) immediately. By Inequality (3) in Corollary E.2, it holds that f f = fA) < 0.377f (0). Let Br, be randomly selected set in Giz, where we calculate Gr, 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& from all the solution set returned by THRESHGUIDEDIG, Suppose that we successfully select set where the inequalities in Lemma E. hold. Then, the recursion of IF [f (B.) can be calculated as follows.
- 1 1 (1-(1-2)) (1))(11111)))
1
(1(O1A)
1 5 5(0u A) ((00A)) -1
I- 2
1 Elf (B:-1)
+
+1
I-e'
+1
1s
[(1-
i- [t26
[B:)] 2
T-
Els (B:-)] +
1
1
-6') -e) ((00)
T-p² +1
En
+1
T-5
- -(1-
(11 2s
(1-2)) r(oua)] (1ou))
Then, by solving the above recursion, it holds that
[f (B(ua)) 2 1 1 (1-1) E2
11) [162])
|t2p]
(1- 1 [162]
((10) +
f(OUA)
- +1
22)
Elf
BB&
1
1
6a((62]
E[f (B(())))))+
+
e21t221
(1-
1
s(0) -1-( (1- 1 l(fal)
S(OUA))
22
I-c +1
5'62
1- (1- (1
@s(tbal)
S10)
1/ +1
E2
I-
1
(1- (1-1)
1 82
1
(O ((o ((OA))))
- -
E2
Ez
(1 - t)l2
1
(1-1)6++1
E2
(1 -t) (1 1- E2
1
(1-1)62
- -(1-2)
1 13)
+
1-
f(0)
f f(OAA)
l +1
22)
l2
+1
E2
1-8
E'62
1- 1 11-(1-
1
(1-1)62+1)
{((0)
(tl2 - 1 < [622 s tt22)
1/ +1
E2
I-ee
1
e c-1- -
- e
12
+ (1 - () 1) (1 (1-
1
((0)
E2
(1- (1-1)--1-
e-1 -11-2)
(1-1)
S(OUA)
1-p +1
12
I +1
E'62
(1- (1-(1-
c-1 f(0)
1-ce +1
(f(On + ( 2 (0) Lemma A.4)
11 ()(22 - 1)
+ +1 _1
(1-
1
c-l c 1-- é -(1 (1-6-1) 5(0)
E2 I-
+1
82
f ((OnA)- - (2--t)e- t)e'
(2
2
1 e-1) ((OUA)
E
36

---

- (62 1)
1
(1-2)
1
+
e' e_ - (1 e
I-c +1
E
1
-0.77 (e'
-) -0.46
(2-t)e'-1
(2 - t)e
2
S(0)
82
(O < 0.377 ( 0.46f (O)
(0.377 -)
0.3; - 5
F
Experiments
Experimental setup We run all experiments on an Intel (eon(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 under minute.
F.1 Additional tables and plots
In this section, you can find the tables and plots omitted in the main paper due to space constraints. In Figure we compare the frames selected by FASTLS +RANDOMGREEDY and STANDARDGREEDY, and in Figure 6, we report the results for Barab' asi-Albert and Watts-Strogatt models for Maximum Cut.
F.2 Problem Formulation
In this section, we formally introduce video summarization and Maximum Cut.
F2.1 Video summarization
Formally, given frames from a video, we present each frame by p-dimensional vector. Let X E Rix" be the Gramian matrix of the resulting vectors Xzy 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" R S(S) log (Xg((()Xxs)) + 1), where Xs is the principal submatrix of indexed by 5 following Banihashem et al. [1] to make the objective function non-monotone non non-negative submodular function.
(a) FASTLS +GUIDEDRG
(b) STANDARDGREEDY
Figure 5: Frames selected for Video Summarization
F.2.2
Maximum cut
Given an undirected graph G(V, E), where V represents the set of vertices, E denotes the set of edges and weights w(u, v) on the edges (u, v) E, the goal of the Maximum Cut problem is to find a subset of nodes V that maximizes the objective function, f(S) -EvSS,ev w(u,v).
F.3 Hyperparameters
For experiments, we set the error rate, e, 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.
37

---

Objective / Greedy
Queries / Greedy
1.0
102
FastLS+GuidedRG
0.9
101
Random Greedy
Leeet-al
100
0.8
0.0
0.2
0.4
0.0
0.2
0.4
k/n
k/n
(a) BA, solution value
(b) BA, queries
Queries / Greedy
103
Objective / Greedy
1.025
102
1.000
0.975
10
0.950
100
0.0
0.2
0.4
0.0
0.2
0.4
k/n
k/n
(c) Watts Strogatz, solution value
(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.
F4 Datasets
The video we select [29] (available under CC BY license) for video summarization lasts for roughly 4 minutes, and uniformly sample 100 frames from the video 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 Erdos-Renyi (ER), Barabasi-Alhert (BA), and Wttts-Strogatz (WS) models. The ER graphs are generated with 0.001, while the WS graphs are created with p = 0.001 and edges per node. For the BA model, graphs are generated by adding m edges in each iteration. Data and code are provided in the supplementary material regenerate the empirical results provided in the paper.
F.5 Implementation of FASTLS+GUDEDRG
For implementation of FASTLS, take the solution of STANDARDGREEDY solution Zo: the theoretical guarantee is thus f(Zo) > OPT/K, since Zo has higher f-value than the maximum singleton. This increases the theoretical query complexity of our algorithm as implemented to O inn log( (g)()) 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 R RANDOMGREEDY [10] to reduce the empirical number of queries further, but for simplicity did not do this in our evaluation.
initial
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made in the abstract and introduction are matched by theorem statements with detailed proofs in the main text and appendices or by empirical evaluation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All formal theorem statements include the assumed hypotheses, and theoretical and empirical limitations are discussed explicitly in Section 5.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer: [Yes]
Justification: All assumptions are clearly specified. the main text, we discuss the intuition behind the analysis and sketch the main arguments, while complete detailed proofs are provided in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All parameter settings and implementation choices for the evaluated algorithms are reported. Further, the source code and documentation provided, with instructions for how to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
40

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
The complete data, source code, and instructions to reproduce the experimental results are provided in the supplementary material. Once this manuscript published, we plan make this available on open-source repository.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https:/ /tttpp::/nipss cc/
public/ /wwic//gues////eeee CodeSubmmi ssioPoliicyy for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (httpa: //nips- cc/ httpcc/ppppbbllc public/ g idee Saee//oddSSSnnn
i oonPol coPolicc) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: No training is involved in the evaluation. All hyperparameters for random graph generation and for the algorithms are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In out plots, we plot the mean over 20 independent repetitions. The shaded regions of the plots indicate one standard deviation about the mean.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
41

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Our experiments are not large-scale, and modern desktop hardware should be sufficient to reproduce all results in few hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eerrpppp.ee
Answer: [Yes]
Justification:
The research conforms in every respect to the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Ours foundational research, not tied to any particular application or de- ployment. The applications upon which we implemented and empirically evaluated our algorithms are proof-of-concepy and thus our provided implementations are unlikely to lead directly to negative socictal impact.
42

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 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 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 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 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: The only pre-existing asset used is the video in the summarization experiment. We explicitly mention the license in Appendix and properly respect the terms.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
43

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papersw thoode com/ dat ssets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 s creators.
13. 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/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. 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 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 contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 crowdsoureing nor research with human subjects.
44

---

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.
45


Reviews:
[{"review_id": "zGcDJY9GKC", "reviewer": "Reviewer_NXWY", "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.", "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?\n\n- Why the dummy elements are needed?\n\n-", "limitations": "Both in Sections 1.1 and 5, the authors discuss the limitations of their work fairly.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper improves the known existing approximation ratios without resorting to continuous algorithms while using the same number of queries. More specifically, they improve the combinatorial approximation ratios of Buchbinder et al. from $1/e \\approx 0.367$ to $0.385 - \\varepsilon \\approx 1/e + 0.018$ for the cardinality constraint and from $0.283$ to $0.305 - \\varepsilon$ for matroid constraints while still requiring $\\mathcal{O}(kn)$ queries. The idea of guiding the RandomgGreedy algorithm with the Fast Local Search (FastLS) is original. The ideas are conveyed clearly and the improvement over the state of the art for combinatorial algorithms is quantifiable.", "weaknesses": "- 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.\n\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments.\n> 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.\n\nWe thank the reviewer for pointing us to this work, which provides an interesting way to approximate the multilinear extension in the case of coverage functions. We will add it to the discussion, and modify the claim as the reviewer suggests.\n\n> 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?\n\nWe apologize for the confusion. InterlaceGreedy is a subroutine of the InterpolatedGreedy of [11] (number 11 of the bibliography in the manuscript). We develop guided versions of it in Alg. 8 and 9 of the appendix.\n\n> 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?\n\nThe LP method relies on a standard lemma for non-monotone submodular functions,\n      which needs a bound on the probability that any element is chosen into the solution.\n      Specifically, Lemma 2.2 of [A] and its generalization in [B]. When the algorithm switches back from the guided\n      behavior to unguided, we were only able to provide a loose upper bound on this probability\n      that wasn't good enough for the analysis. In particular, we had difficulty ordering the\n      the probabilities of the elements in a way that would allow us to apply the lemma.\n      It is possible that a generalization of Lemma 2.2, or a clever way of considering\n      the probabilities is possible and that the LP method could be used.\n\n[A]: Feige et al. Maximizing Non-monotone Submodular Functions. SIAM Journal on Computing 40 (4).\n\n [B]: Buchbinder et al. Submodular Maximization with Cardinality Constraints. SODA 2014. \n\n> Why are the dummy elements needed?\n\n We introduce dummy elements to simplify both the pseudocodes and the analysis.\n      The simplification comes from the fact that we may assume that an optimal\n      solution is of size $k$, or a base of the matroid, by adding dummy elements.\n      Moreover, our set $M_i$ in RandomGreedy\n      of the top $k$ marginal gains has $k$ non-negative gains. Otherwise, we would\n      have to allow $M_i$ to potentially be smaller and adjust the probabilities of elements,\n      for example: choose no element with some probability, and one of the remainder\n      uniformly randomly. This would create more cases in the analysis and complicate the\n      picture unnecessarily.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IU77wTDIME", "reviewer": "Reviewer_95ga", "summary": "This paper studies the classical problem of maximizing a non-monotone submodular function subject to a cardinality and a matroid constraint.\nA 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).\nThe more practical combinatorial algorithms have not been able to break the $1/e$ barrier.\n\nThe main contribution is a suite of algorithms which work via an \"guided\" local search procedure.\nThe 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. \nIf the parameters of the algorithm is appropriately set, at least one of these two solutions is of high (expected) quality.\nThe 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.\n\nThere 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$.\nSimulations are run comparing the algorithms to two reasonable benchmarks.", "questions": "I thank the authors for their manuscript and invite them to respond to the points raised in my review. \nHowever, I do not feel that I have any questions to raise at this time.", "limitations": "All limitations sufficiently addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The main strength of the work is in the development of simple algorithms with improved approximation ratios for submodular maximization.\nIn particular, the randomized algorithm achieving $0.385-\\epsilon$-approximation for cardinality constraint and $0.305-\\epsilon$ approximation for matroid constraint is the main contribution of the paper.\nOf particular note is that this algorithm is analyzed for both cardinality and matroid constraints, though different switching times $t$ should be used.\n\nI really enjoyed the clarity of the writing in Section 2.2 which provided intuition for the theoretical results.", "weaknesses": "**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.\n\n**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:\n\n- The objective functions are not presented and the movie summarization dataset is not discussed.\n- 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?\n- 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?\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful feedback. We respond to each point below.\n> 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.\n\nWe apologize for the difficulty. Due to space constraints, it was difficult to decide what\n  should be presented in the main text vs. the appendices. We decided 1) to limit the main\n  text to the size constraint, as it is more accessible than the matroid constraint,\n  and 2) to try to explain the most important ideas in the main text at a high level, and\n  leave the formal analysis to the appendix. However, this means we sometimes refer to\n  lemmas, etc., in the appendix, which decreases readability. In the next revision, we will\n  make a further refinement in the hope of increasing readibility further and to minimize\n  the necessity of consulting back and forth between the appendices and main text. \n\n> The objective functions are not presented and the movie summarization dataset is not discussed.\n\nDue to space constraints, the objective functions for each application,\nand the movie summarization dataset details are discussed in Appendix F.\nWe will make this more clear in the next version. \n\n> 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?\n\nIn the main text, we only present the results on ER graphs.\nThe results on the other two models are provided in Fig. 6 in Appendix F. \nWe will add references in the experiment section to clarify.\n\n> 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?\n\nThank you for asking this. Interestingly, it turns out that the objective value of our algorithm is usually dominated by\nthe local search subroutine, which is deterministic. Thus, there is little variance\nin the objective value, which is why the error bars are not visible (they are there).\nFor the runtime, the number of queries of GuidedRG is deterministic.\nThus, the number of queries of our main algorithm is deterministic.\n\n> 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.\n\nIn our results, we observe an improvement over Greedy of up to 2\\%,\nwhich in our opinion is significant.\nHowever, we agree that we could have chosen applications, perhaps weakly submodular ones,\nin which further improvement on Greedy is possible. Analyzing our algorithms in the weakly submodular case both theoretically and empirically is an interesting avenue for future work.\n\nIn addition, Greedy does not guarantee a constant approximation ratio for non-monotone submodular maximization problems.\nCompared to those algorithms which do provide constant approximation ratio,\nour algorithm outperforms RandomGreedy with respect to the objective value,\nand outperforms Lee et al.'s LocalSearch with respect to the query complexity.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yWZFYRilvK", "reviewer": "Reviewer_qSWx", "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.", "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": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides two new deterministic algorithms with approximation ratio better than 1/e.\n2. The paper provides practical randomized algorithm with both theoretical analysis and experimental evaluation.", "weaknesses": "1.\tThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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.\n \nThank you for bringing this paper to our attention; we note that\n  it was released on arXiv after the submission deadline\n  for NeurIPS 2024. Also, we would like to respectfully point out the\n  policy of NeurIPS concerning contemporaneous work.\n  \nIndeed, the authors of arXiv:2405.13994 had a similar goal to our work,\n  namely to produce practical algorithms with guarantee larger than $1/e$.\n  It appears to be a case of independent, parallel work. \n  Broadly speaking, the main idea of the two works is similar -- to develop\n  methods to guide the random greedy algorithm with a fast algorithm to\n  find a local optimum.\n  Our local search procedure is deterministic, while theirs is randomized\n  and uses different ideas. Their local search\n  is faster for small $k$ values. They also guide a faster variant of\n  RandomGreedy to achieve their overall time complexity of\n  $O(n + k^2)$.\n\nOn the other hand,\n  in our work, we 1) develop a guided algorithm\n  for matroid constraints;  2) for size constraint,\n  we have an asymptotically faster algorithm that uses a novel\n  way of guiding with partial solutions from random greedy itself,\n  which are not local optima, thereby achieving ratio $0.377$ in $O_{\\epsilon}(n \\log k)$;\n  and 3) we derandomize. \n  For 1) and 2), we had to develop novel recurrences to analyze\n  random greedy, which depart further from the\n  original guiding and analysis of the continuous measured greedy algorithm\n  to achieve ratio $0.385$. Random greedy for matroids is much\n  more like a local search algorithm than a greedy algorithm,\n  as the best swap is made at each iteration. \n  In particular, the guided recurrences stated in Lemmas C.5 and C.6\n  for the matroid constraint, and their closed form solution in\n  Lemma C.7, as illustrated in Fig. 4.\n  Further, derandomization for the matroid constraint\n  required development of Algorithm 8 and its analysis in\n  Lemma D.1. For 2), we think the use of random greedy to\n  guide itself is interesting, and we believe the resulting\n  analysis (depicted in Fig. 2) aids in the understanding\n  of the random greedy algorithm, perhaps opening up further\n  uses such as bicriteria algorithms, etc. Although the deterministic version has poor dependence on $\\epsilon$, this idea might be used to produce a faster randomized version of this algorithm in subsequent work.\n  \nIn future versions of our paper, we will add a citation to this independent, parallel work\n  and a discussion of the technical relationship.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bBEZvT3Eat", "reviewer": "Reviewer_arzS", "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. \n\nThe paper has the following contributions:\nfor cardinality constraints:\n- 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$\n- 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$. \n- 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. \nfor matroid constraints: \n- 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$\n- the previous best combinatorial algorithm provided a $0.283$ approximation, while the overall state of the art is a continuous $0.41$-approximation.", "questions": "None", "limitations": "The paper has no potential negative societal impact", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Submodular maximization is an important problem to the ICML and NeurIPS  community, with many practical applications and a rich literature in these conferences\n- Closing the approximation gap for non-monotone submodular functions is an exciting research question. To get some context, the current state of the art, i.e., the 0.401 approximation by Buchbinder and Feldman, has recently been presented at STOC, one of the top conferences in theoretical computer science\n- finding combinatorial algorithms is important as continuous algorithms are impractical to implement and extremely expensive in terms of queries to the submodular function", "weaknesses": "the deterministic algorithms are impractical, as they feature an exponential dependence on the approximation parameter $1/\\varepsilon$. Their relevance is mainly theoretical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for the contructive comments. We hope that we were able to answer the questions of all reviewers in our individual responses. To summarize,
in the next version, 
- we will make efforts to improve the readability of the paper by minimizing the necessity of consulting the appendix to understand the theoretical results. 
- In the experimental section, we will add more pointers to the appendix to clarify settings and results that are omitted from the main text for space reasons. 
- We will add citation of the contemporaneous work [1].
We note that [1] appeared on arXiv on 22 May 2024,
20:56 UTC, after the NeurIPS 2024 submission deadline,
at 22 May 2024, 20:00 UTC -- thus, there was no way for
us to address this paper in the submitted manuscript. 
We discuss in detail the differences between the two works in our response to Reviewer qSWx, and a version of this discussion will be added to the paper.

[1]: Tukan et al. Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint. arXiv:2405.13994

Meta-review: 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.
Decision: Accept (poster)