Efficient Parallel Algorithms with Linear Queries for Non-Monotone Submodular Maximization

1 Introduction

Maximizing a non-negative (not necessarily monotone) submodular set function under a cardinality constraint is a fundamental problem with broad applications in artificial intelligence and machine learning. Notable examples include data summarization [Kuhnle, 2021; Lin and Bilmes, 2011; Fahrbach et al., 2019a; Han et al., 2021; Mirzasoleiman et al., 2016], revenue maximization in social networks [Kuhnle, 2021; Chen and Kuhnle, 2023], recommendation systems [Mirzasoleiman et al., 2016], and weight cut problems [Chen and Kuhnle, 2023; Kuhnle, 2021].

∗Corresponding author

Formally, given a finite ground set V of size n, a submodular set function f : 2V → R+, and a positive integer k representing the cardinality constraint, the goal of the Submodular Maximization under a Cardinality Constraint (SMC) problem is to find a subset S ⊆ V such that |S| ≤ k and f(S) is maximized. This problem has attracted extensive attention, with many works focusing on developing approximation algorithms with provable performance guarantees [Buchbinder et al., 2014; Kuhnle, 2019; Chen and Kuhnle, 2023].

However, the exponential growth of the solution space with the input size poses a significant computational challenge, particularly in modern large-scale applications. This has spurred growing interest in designing efficient parallel algorithms capable of leveraging modern parallel computing architectures to compute high-quality solutions rapidly (see Table 1 for a summary of parallelizable methods). In this context, the concept of adaptive complexity (or adaptivity) has emerged as a key metric for assessing the parallel efficiency of such algorithms. A central notion in assessing the parallel efficiency of such algorithms is adaptive complexity (or adaptivity), which measures the number of sequential rounds an algorithm requires, allowing a polynomial number of oracle queries to be processed in parallel during each round [Balkanski and Singer, 2018]. Notably, reducing the adaptive complexity from O(log2 n) to O(logn) has been shown to significantly cut down the number of sequential steps, resulting in notable improvements in practical runtime performance [Fahrbach et al., 2019a; Ene and Nguyen, 2020; Amanatidis et al., 2021; Fahrbach et al., 2023; Kuhnle, 2021; Chen and Kuhnle, 2024]. Although recent advances have successfully brought down the adaptive complexity to O(log n), several significant challenges remain: (1) The high query complexity made the some parallel algorithms with O(log n) adaptive complexity impractical for real applications. For instances, [Chen and Kuhnle, 2024] demonstrated that the algorithm in [Ene and Nguyen, 2020] providing the best ratio of 1/e - ϵ within O(log n) adaptivity is of mostly theoretical interest because it needs Ω(nk2 log2 (n)) queries to approximate the multi-linear extension of a submodular function and its gradient.

(2) The approximation ratios of the existing practical parallel algorithms [Fahrbach et al., 2019a; Fahrbach et al., 2023; Kuhnle, 2021; Chen and Kuhnle, 2024; Cui et al., 2023] are still low as they have a large gap in the approximation ratios compared to the best non-parallel algorithm for SMC (e.g. the ratio of 0.401 in [Buchbinder and Feldman, 2024]). This raises two interesting questions for us to solve SMC: Can we improve the query complexity and approximation ratio of a practical parallel algorithm?

Our contributions and techniques. In thiswork, we tackle the above questions with the following contributions:

First, we introduce LinAdapt, the first constant approximation ratio (1/(12 + O(ϵ))) within near-optimal adaptivity O(log n) and linear query complexity O(n), where ϵ > 0 is a constant parameter. LinAdapt is used as a building block to reduce the query complexity of our latter algorithms. The key idea to obtain a such improvement lies in: (1) constructing two sets S, S′ in O(log n) sequential rounds with an interesting property: f (X ∪ S) ≤ O(1) · f (S′ ) with high probability for any set X ⊆ V, |X| ≤ k, and S′ with |S′ | ≤ k is the set of last elements added into S; (2) combining (1) appropriately with the unconstrained submodular maximization algorithm to get the desired ratio.

Second, we introduce two algorithms LinAst and LinAtg which run O(logn) adaptivity and O(n) query complexity and return the approximation ratios to 1/6 - ϵ and 0.193 - ϵ, respectively. Therefore, our algorithm LinAtg improves the approximation ratio from 0.172 - ϵ to 0.193 - ϵ and significantly reduces the query complexity of the current best practical algorithm of [Amanatidis et al., 2021].

Third, we propose a practical algorithm, denoted by BoostAdapt, that achieves an approximation ratio of 1/4 - ϵ with O(logn log k) adaptive complexity and O(n log k) query complexity. As a result, BoostAdapt improves the best-known approximation ratio for algorithms with the same adaptive and query complexity from 0.193 - ϵ to 0.25 - ϵ. The design of BoostAdapt is inspired by the twin greedy strategy, which incorporates ThreSeq to update two disjoint sets, X and Y , in an alternating manner over only O(log k)

iterations. It must be noted that the staggered threshold is different from the Iterated Greedy [Gupta et al., 2010], which uses two threshold greedy strategies to construct candidate solutions separately.

Finally, to show the consistency between theory and practice, we conducted extensive experiments on two applications: Revenue Maximization and Maximum Weighted Cut. The results show that our algorithms not only produce the better solution quality and query complexity sharply but also provide comparative adaptivity to state-of-the-art algorithms. Paper Organization. The rest of this work is structured as follows. Section 2 provides the literature review on the studied problem. Notations are presented in Section 3. Sections 4-6 introduce our algorithms and theoretical analysis. Experimental computation is provided in Section 7. Finally, Section 8 concludes this work.

2 RelatedWork

Approximation Algorithms. The first popular approach to solving the SMC problem in practice is to design approximation algorithms with low query complexity. The greedy algorithm was an effective approach for submodular optimization problems. It sequentially selects elements with the largest marginal gain and explores the diminishing return property to get performance bounds. [Gupta et al., 2010] first developed an iterated greedy algorithm with 1/6 ratio in O(nk) queries for SMC. The work of [Lee et al., 2010] latter improve the ratio to 1/4 - ϵ by developing a local search method but this wasted an expensive query complexity of O(n4 logn). Significantly, the elegant random greedy in [Buchbinder et al., 2014] could provide the ratio of 1/e with O(nk) query complexity. Instead of selecting an element with the best marginal gain as the naive greedy, it chose a uniformly random element from the set of k elements with the largest marginal gain. [Buchbinder et al., 2015] then improved the query complexity to O(n log(1/ϵ)/ϵ2 ) but still kept the same 1/e ratio.

Recently, independent works [Chen et al., 2025] and [Tukan et al., 2024] improved the ratio to 0.385-ϵ in O(n2 ) queries and O(n) adaptive complexity. To the best of our knowledge, the best ratio for SMC was 0.401 by [Buchbinder and Feldman, 2024]. However, this work used the multi-linear extensions method and used a considerably high query complexity of O(n5 ) [Chen and Kuhnle, 2023]. Finally, it must be emphasized that the above works weren't well parallelized due to their high adaptive complexities of Ω(n).

Parallel Algorithms. Research on parallel algorithms was initiated by [Balkanski and Singer, 2018]. In this seminal work, they introduced the concept of adaptive complexity or adaptivity that measures the parallelizable of algorithm, showed a lower bound on adaptive complexity of O(log(n)/ log(log n)) to achieve a constant ratio and devised an 1/3-approximation algorithm in O(log n) adaptive rounds for the monotone SMC problem. Since then, many works focused on devising algorithms with low adaptivity with tighter ratio for SMC [Balkanski et al., 2019; Fahrbach et al., 2019b; Ene et al., 2019; Chen et al., 2021]. The best parallel algorithm for monotone SMC had an optimal ratio of 1 - 1/e - ϵ in O(log n) adaptivity and O(n) queries was due to [Chen et al., 2021]. However, their performance bounds relied on the monotone objective and did not hold for non-monotone.

For the non-monotone SMC, [Chekuri and Quanrud, 2019; Balkanski et al., 2018] first developed parallelizable algorithms with 3 - 2√2 - ϵ and 1/(2e) - ϵ ratios, respectively; both took O(log2 n) adaptivity. [Ene and Nguyen, 2020] improved the ratio to 1/e-ϵ in nearly optimal adaptive complexity of O(logn). However, due to the high query complexity of Ω(nk2 log2 n) to approximate the multilinear extension of a submodular function and its gradient, the [Ene and Nguyen, 2020]' algorithm and algorithms based on multilinear extension methods in general are still impractical in some real applications [Kuhnle, 2021; Fahrbach et al., 2019a; Chen and Kuhnle, 2024; Cui et al., 2023]. To attack the above issue, [Fahrbach et al., 2019a] first aimed to reduce the query complexity to near-linear of O(n log k) and still kept the O(log n) adaptive complexity. However, their algorithm resulted in a small ratio, 0.039 - ϵ. In subsequent work, [Kuhnle, 2021] tried to boost the ratio to 1/6-ϵ in O(log n) adaptive rounds with O(n log k) queries. Their algorithm further improved the ratio to 0.193-ϵ in O(log2 n) adaptive rounds by exploring iterated greedy framework in [Gupta et al., 2010]. It must be noted that the ratios of both [Fahrbach et al., 2019a] and [Kuhnle, 2021] may not hold because they adapt the threshold sampling routine in [Fahrbach et al., 2019b], which was pointed out disable with non-monotone functions [Chen and Kuhnle, 2024]. Recently, [Chen and Kuhnle, 2024; Fahrbach et al., 2023] recovered the ratios of [Fahrbach et al., 2019a; Kuhnle, 2021] by some threshold sampling routines with the respective analysis. [Cui et al., 2023] then showed two algorithms with ratios of 1/8 - ϵ and 1/4 - ϵ with O(log n) and O(log2 n) adaptive complexities, respectively. However, they took at least Ω(nk log2 n) query complexity. More recently, [Chen et al., 2025] proposed two parallel algorithms, PIG and PITG, which achieve approximation ratios of 0.25 and 1/e-ϵ, respectively. Both algorithms takes a query complexity of O(n log(n) log(k)) and an adaptive complexity of O(log(n) log(k)).

3 Preliminaries

Given a ground set V of size n, and the set function f : 2V ↦→ R+ is submodular iff it satisfies the diminishing return property, i.e., f(A ∪ {e}) - f(A) ≥ f(B ∪ {e}) - f(B) where A ⊆ B and e /∈ B. The marginal gain (or contribution gain) of a set T to a set S is defined as f(T |S) = f(T ∪S)-f(S). For simplicity, we denote f({e}|A) by f(e|A) and assume f normalized, i.e., f(∅) = 0. Given a positive number k (cardinality constraint), the SMC problem is to determine arg maxS⊆V,|S|≤k f (S).

We define [k] = {1, 2, . . . , k} for any integer k. We denote an instance of SMC by a tuple (f, V, k) and O is an optimal solution with the optimal value opt = f(O). In this work, we assume that there exists an oracle query that returns f(S) when queried for the set S with any S ⊆ V . The parallelization capacity of an algorithm is evaluated through the following definition.

Definition 1 ([Balkanski and Singer, 2018]). The adaptivity or adaptive complexity of an algorithm is the minimum sequential number of rounds needed such that in each round the algorithm makes O(poly(n)) independent queries to the evaluation oracle.

We recap two sub-problems for solving SMC in parallel setting, Batch Selection with Threshold (BST) and unconstrained submodular maximization (USM). Given an instance (f, V,B), a fixed threshold τ and ϵ > 0 as inputs, BST asks to find a subset S ⊆ V in O(log n) adaptive complexity satisfying two conditions: (1) f(S) ≥ (1-ϵ)τ|S|; (2) if |S| < k, f(e|S) < τ for any e /∈ S.

Although several attempts exist to solve the BST, most only work with a monotone submodular function [Fahrbach et al., 2019b; Kazemi et al., 2019]. In this work, we use the ThreSeq algorithm in [Chen and Kuhnle, 2024] and its theoretical satisfaction to analyze our algorithm's performance in a nonmontone setting.

Theorem 1 (Theorem 3 in [Chen and Kuhnle, 2024]). Let (f, V, k) be an instance of SMC. For any constants ϵ, δ > 0, the algorithm ThreSeq outputs A′ ⊆ A ⊆ V such that the following properties hold: 1) The algorithm succeeds with probability at least 1 - δ/n. 2) There are O(n/ϵ) oracle queries in expectation and O(log(n/δ)/ϵ) adaptive complexity. 3) It holds f(A′ ) ≥ (1 - ϵ)τ|A|. If |A| < k, then f(e|A) < τ for all e ∈ V . 4) It also holds f(A′ ) ≥ f(A) and |A′ | ≥ (1 - ϵ)|A|.

Regarding USM, which aims to find argmaxS⊆V f(S), there exist several solving methods giving the constant approximation ratios such as the [Fahrbach et al., 2019a]'s algorithm (USM1) provides a ratio of 1/4 - ϵ with probability at least 1 - δ for the problem in O(1) adaptive round and O( 1ϵ log( 1δ )) queries and an essentially optimal algorithm of [Chen et al., 2019] (USM2) slightly improves the approximation ratio to 1/2-ϵ using O(log(1/ϵ)/ϵ) adaptive rounds and O(n log3 (1/ϵ)/ϵ4 ) query complexity.

4 A Parallel Algorithmwith Linear Queries

In this section, we introduce LinAdapt (Algorithm 1), the first constant ratio approximation algorithm within O(log n) adaptivity and O(n) query complexity. LinAdapt receives

Algorithm 1: LinAdapt(f, V, k, α, ϵ, δ)

• 1: Input: f, V , k, α, ϵ, δ.
• 2: A, A′ ← LinBoundSet(f, V, k, α, ϵ, α, δ/3)
• 3: B, B′ ← LinBoundSet(f, V \ A, k, α, ϵ, δ/3)
• 4: C ←USM1(A, ϵ, δ/(3n))
• 5: Return argmaxS∈{A′ ,B′ ,C} f(S)

an instance (f, V, k), accuracy parameters ϵ, δ > 0, a constant α > 0 and works in a novel algorithmic framework. LinAdapt first sequentially calls a subroutine LinBoundSet twice to find two candidates: one to get A over the ground set V and the other to get B′ over a new ground set V \ A. Note that A and B in LinAdapt are temporary sets that are useful only for theoretical analysis. For any ground set V , LinBoundSet is a key subroutine with the following nice properties:

1. running in O(log(n)/ϵ2 ) and O(n/ϵ3 ) query complexity.
2. returning two sets A and A′ so that f(A ∪ X) ≤ (8 + 2α + 2α +O(ϵ))f(A′ ), for any subset X ⊆ V, |X| ≤ k with high probability.

To easily follow the algorithm, we will latter provide a detailed analysis of LinBoundSet in Section 4. Finally, LinAdapt calls USM1 to find another candidate solution C and returns the best among A′ ,B′ ,C. Conceptually, our LinAdapt takes advantage of the properties LinBoundSet (by Theorem 3), and the fact that f(O) ≤ f(O∪A)+f(O∪B) to give the desired bound of solution. We state the LinAdapt's performance in Theorem 2.

Theorem 2. For any input (f, V, k), where ϵ, δ ∈ (0, 1), LinAdapt runs in O(log(n/δ)/ϵ2 ) adaptive complexity and O(n/ϵ3 ) query complexity, returns a solution S satisfying opt ≤ (8+2α+ 2α +( 16 1-4ϵ +2(1+ 1α ) 2(2-ϵ) (1-ϵ)(1-2ϵ) )ϵ)f (S) with probability at least 1 - δ/n. If α = 1, the algorithm achieves the best ratio of 1 12+O(ϵ) .

Proof. Each subroutine terminates with failure probability 1/(3n). By the union bound of probabilities, the failure probability of the algorithm is bounded by 3 · δ 3n = δn . Let a = 2 + α + 1α + (1 + 1α ) 2(2-ϵ) (1-ϵ)(1-2ϵ) ϵ. If the algorithm terminates successfully, we have:

where inequality (1) is due to the submodularity of f and the fact that A ∩ B = ∅; the inequality (2) is due to the submodularity of f, and the inequality (4) is due to Theorem 3 and USM1's performance. For the complexities, the algorithm calls USM1 and LinAdapt twice so its adaptive complexity is 2 · O( log n ϵ2 ) + 1 = O( logn ϵ2 ) and query complexity is 2 · O( n ϵ3 ) +O( 1ϵ log( nϵ )) = O( n ϵ3 ).

Algorithm 2: LinBoundSet(f, V, k, α, ϵ, δ)

• 1: Input: f, V , k, α, ϵ, δ
• 2: emax ←maxe∈V f(e), S ← {emax}, β ← ϵ log((1 - e -ϵ 2 )/8)/16, ℓ ← ⌈(4+ 4 βϵ ) log( nδ )⌉
• 3: for j ← 1 to ℓ do
• 4: V ← {x ∈ V : f(x|S) ≥ αf(S)/k}
• 5: If V = ∅ then break;
• 6: V = {v1, v2, . . . , v|V |} ← rand-permutation(V )
• 7: Λ1 ← {⌊(1+ ϵ)l ⌋ : 1 ≤ ⌊(1+ ϵ)l ⌋ ≤ k, l ∈ N}
• 8: Λ2 ← {⌊k + lϵk⌋ : ⌊k + lϵk⌋ ≤ |V |, l ∈ N} ∪ {|V |}
• 9: Λ = {λ1, . . . , λm} ←Λ1 ∪Λ2, Ti = {v1, v2, . . . , vi}, T ′λi ← Tλi \ Tλi-1
• 10: Calculate Mλi ←maxλj≤λi f(S ∪ Tλj ) in parallel
• 11: b[vi] ← none, ∀vi ∈ V ; B[λi] ← false, ∀λi ∈ Λ
• 12: for λi ∈ Λ (in parallel) do
• 13: for vl ∈ T ′λi (in parallel) do
• 14: if f(vl|S ∪ Tl-1) ≥ (1 - ϵ)αMλi-1 /k then b[vl] ← true
• 15: else if f(vl|S ∪ Tl-1) < 0 then b[vl] ← false 16: end for
• 17: if |{v ∈ T ′λi : b[v] = true}| ≥ (1- ϵ)|T ′λi | then B[λi] ← true
• 18: end for
• 19: λ∗1 ←max{λi ∈ Λ, λi < k : B[λi] = false,B[λ1] = B[λ2] = . . . = B[λi-1] = true}
• 20: λ∗2 ←max{λi ∈ Λ, λi ≥ k : ∃u ≥ 1 s.t.| ⋃i-1 j=u T ′λj | ≥ k and (B[λu] = B[λ2] = . . . = B[λi-1] = true}
• 21: λ∗ ←max{λ∗1 , λ∗2 }
• 22: Define new blocks T ′′ λi ← {v ∈ T ′λi : b[v] ̸= false}
• 23: T j ← ⋃λi≤λ∗ T ′′ λi , S ← S ∪ T j , V ← V \ ⋃λi≤λ∗ T ′λi
• 24: end for
• 25: If |V | > 0, then Return failure
• 26: S′ ← last blocks added into S with the size at most k
• 27: Return S, S′

A key subroutine LinBoundSet (Algorithm 2). It receives an instance (f, V, k), accuracy parameters ϵ, δ > 0 and a positive constant α. It first initiates a set S that contains an element with maximal value emax and then operates in ℓ = O(logn) iterations of the main loop (Lines 3-24). Denote Sj as S after iteration j. At each iteration of main loop, it generates a random permutation of V (Line 6) and divides V into blocks T ′λi , ∀λi ∈ Λ. We define an element vt ∈ T ′λi that is good if f(vt|{v1, . . . , vt-1}) ≥ αMλi /k, where Mλi = maxj=0...i f(S ∪ Tλj ), i ∈ [m]; a block T ′λi is good if it has at least (1 - ϵ)α|T ′λi | good elements.

At a high level, at iteration j, the algorithm selects a segment of elements Tλ∗ and its subset T j (Line 23) from set T, a random permutation of V satisfying three following requirements with high probability: (1) |T j | ≥ (1 - ϵ)|Tλ∗|; (2) f(T j |S) ≥ (1 - O(ϵ))α|Tλ∗ |f(S)/k; and (3) remove elements in V with the marginal gain is less than αf(S)/k, i.e., f(e|S) < αf(S)/k for all e ∈ V \ S.

To achieve the requirements, we propose the strategy to select a pair of good subset S and S′ in algorithm 2 as follows: It first removes every element whose marginal gain is less than αf(S)/k (Line 4); later, it selects Tλ∗ , a consecutive sequence of elements T that contains at least (1 - ϵ)-fraction number of blocks that are good by finding λ∗ in Line 19. Then, it selects new block T ′′ λi that only contains elements with non-negative marginal gain from T ′λi and selects all new blocks from Tλ∗. At the end of each iteration, it adds Tj into S and the main loop ends after ℓ iterations or V is empty. Finally, the algorithm returns S′ as the union of last T ′′ λi blocks added to S so that the size of S′ does not exceed k (Line 23).

By combining the our selection strategy for subsets S and S′ with the analysis of probability bounds in [Chen et al., 2021; Chen and Kuhnle, 2024], we provide the analysis LinBoundSet's performance in following process. We first focus on the bridge between S and S′ in Lemma 1.

We define an iteration j succeeds if the algorithm successfully filters out more than βϵ-fraction of V at the next iteration. Otherwise, the iteration j fails. The following Lemma provides a bound of probability for the event that iteration j fails.

Lemma 2. Pr[iteration j fails ] ≤ 1/2.

Combine Lemma 1 and Lemma 2, we state the performance of LinBoundSet in Theorem 3.

Theorem 3. For any ϵ, δ ∈ (0, 1), the algorithm LinBoundSet runs in O(log(n/δ)/ϵ2 ) queries, returns two sets S and S′ such that the following holds unconditionally: (1) The algorithm succeeds with a probability of at least 1 - δ/n; (2) The algorithm takes O(n/ϵ3 ) query complexity in expectation; (3) If the algorithm succeeds, it returns S, S′ satisfying: for any subset X ⊆ V, |X| ≤ k, we have f(S ∪X) ≤ (2+α+ 1α + (1+ 1α ) 2(2-ϵ) (1-ϵ)(1-2ϵ) ϵ) f (S′ ).

5 Improved Ratio with Linear Queries

This section introduces two combinatorial algorithms within linear query and near-optimal adaptivity complexities: LinAtg and LinAst. Both share a common framework in which LinAdapt plays a central role and provides O(1) number of guesses of the optimal value. Firstly, they adapt LinAdapt with α = 1, δ = 1/3 to give a candidate solution S0 with opt ∈ [f(S0), (12 + O(ϵ))f(S0)]. It thus provides O( 1ϵ log( 1ϵ )) guesses of opt. They then use the Adaptive Simple Threshold (AST) framework [Chen and Kuhnle, 2024]

and the Iterated Greedy (IG) algorithm framework [Gupta et al., 2010; Chen and Kuhnle, 2024] to boost the ratio.

LinAst constructs several solutions in the main loop with O( 1ϵ log( 1ϵ )) adaptive rounds: each iteration i calls ThreSeq twice sequentially to get candidate solutions A′i , B′i . It finally combines the obtained solution and the solution of USM over A′i to get the final solution. LinAtg works in a different way. It sequentially constructs two pairs of disjoint sets (A, B) and (A′ , B′ ) in two main loops which contain at most ℓ = O( 1ϵ log( 1ϵ )) iterations: each iteration calls ThreSeq to select two batches of elements with high marginal gain (S, S′ ) and adds them into (A, A′ ) (or (B, B′ )), respectively. It also the solution of USM over A′ and finally returns the best one among the obtained feasible solutions. We provide the performance of LinAtg and LinAst in Theorems 4, 5.

Theorem 4. For any input (f, V, k, ϵ), where ϵ ∈ (0, 1), LinAst runs in O(log(n)/ϵ2 ) adaptive complexity and O(n/ϵ3 ) query complexity and returns an approximation ratio of 1/6 - ϵ in expectation with probability of at least 1 - 1/n.

Theorem 5. For any input (f, V, k, ϵ), where ϵ ∈ (0, 1), LinAtg runs in O(log(1/ϵ) log(n)/ϵ2 ) adaptive complexity and O(n/ϵ3 ) query complexity, returns an approximation ratio of 0.193 - ϵ in expectation with probability of at least 1 - 1/n.

6 Boost Ratio with Near-Linear Queries

This section introduces our last algorithm, BoostAdapt (Algorithm 3), which further improves the ratio to 1/4 - ϵ in O(log(n) log(k)) adaptivity and O(n log(k)) query complexity. Different from LinAtg and LinAst, after reusing LinAdapt's solution, BoostAdapt operates in a novel staggered strategy that consists of a main loop with O(log(k/ϵ)/ϵ) iterations. It initiates two pair of disjoint sets: (X, Y ) and (X′ , Y ′ ). At each iteration, it only updates alternatively partial solutions, either X,X′ or Y, Y ′ , by calling ThreSeq. The algorithm then carefully selects candidates X′′ and Y ′′ that consist of min{k, |X′ |} and min{k, |Y ′ |} from X′ and Y ′ , respectively. Finally, it returns the best among candidates without violating the cardinality constraint.

At a high level, our BoostAdapt algorithm do not adapt USM algorithms (may make the approximation ratio worse) and operates differently from Iterated Greedy [Gupta et al., 2010], which inspired AdaptiveThresholdGreedy of [Kuhnle, 2021; Chen and Kuhnle, 2024]. BoostAdapt is an elegant combination between threshold greedy [Badanidiyuru and Vondr´ak, 2014] and twin greedy [Han et al., 2020] via using ThreSeq procedures alternatively to update two disjoint solutions X and Y . Interestingly, we found that X and Y can support each other to bound elements in the optimal solution. Besides, by carefully analyzing the role of the set X after the first iteration (i.e., X1), we can give a better ratio than previous algorithms with the same complexities.

Before analyzing the BoostAdapt's performance, we provide some useful notations as follows: Xi , Y i are the sets of first i elements added into X and Y , respectively; Xi and Yi are X and Y after the iteration i of the main loop and X0 = Y0 = ∅; X′ i and Y ′ i are defined analogously; A+i (res.

Algorithm 3: BoostAdapt

• 1: Input: f, V , k, ϵ.
• 2: S0 ← LinAdapt(f, V, k, 1, ϵ, 1/3), a ← 12+ ( 16 1-4ϵ + 8(2-ϵ) (1-ϵ)(1-2ϵ) )ϵ
• 3: M ← af(S0), ∆← ⌈log 1 1-ϵ ( ak 4ϵ )⌉ + 1, δ ← 1/(3∆)
• 4: X, X′ , Y, Y ′ ← ∅, k′ ← max{i ∈ N : (1 - ϵ)i ≤ k}, τ ← k′M 4k
• 5: for i ← 1 to ∆ do
• 6: if i is odd then
• 7: τX ← τ (1 - ϵ)i , (Ai, A′i ) ← ThreSeq(f (X ∪ ·), V \ (X ∪ Y ), k′ - |X|, ϵ, δ, τX),
• 8: X ←X ∪Ai, X′ ←X′ ∪A′i
• 9: else
• 10: τY ← τ (1 - ϵ)i , (Bi, B′i ) ← ThreSeq(f(Y ∪ ·), V \ (X ∪ Y ), k′ - |Y |, ϵ, δ, τY ),
• 11: Y ← Y ∪Bi, Y ′ ← Y ′ ∪B′i
• 12: end if
• 13: end for
• 14: Define X′ = {x′1 , x′2 , . . . , x′|X′ | },
• Y ′ = {y′1 , y′2 , . . . , y′ |Y ′ | } contain elements in the order selected.
• 15: X′′ ← set of min{k, |X′ |} elements x′i ∈ X′ with largest marginal gain f(x′i |X′<x′i )
• 16: Y ′′ ← set of min{k, |Y ′ |} elements y′i ∈ Y ′ with largest marginal gains f(y′i |Y ′<y′i )
• 17: S ← argmaxZ∈{X′ ,Y ′ ,X′′ ,Y ′′ ,S0},|Z|≤k f(Z)
• 18: Return S

B+ i ) as the set of elements inAi (res. Bi) having themarginal gain at least τX (res. τY ) at the iteration i, X+ i = ∪ij=1A+i , Y + i = ∪ij=1B+ i and X+ =X+ ∆ , Y + = Y + ∆ .

By the properties of ThreSeq [Chen and Kuhnle, 2024], it is noted that |A+i | ≥ (1-ϵ)|Ai|, |B+ i | ≥ (1-ϵ)|Bi|. For an element e ∈ X ∪ Y , we denote by X<e , Y <e as X, Y right before e is selected into X or Y , respectively.

We now analyze theoretical bounds of BoostAdapt algorithm. Firstly, we explore some basic properties of X, X′ , X′′ and Y, Y ′ , Y ′′ according to the iteration i of the main loop.

Lemma 3. a) For any iteration i of the outer loop (Lines 513) of Algorithm 3, we have f(X′ i ) ≥ f(Xi) and f(Y ′ i ) ≥ f(Yi). b) At the end of BoostAdapt, we have f(X′′ ) ≥ (1 - ϵ)f(X′ ) and f(Y ′′ ) ≥ (1 - ϵ)f(Y ′ ).

By carefully analyzing the relationship between X and Y through thresholds, we provide the connection between X and Y after each iteration in Lemma 4.

Lemma 4. If BoostAdapt succeeds and X1 = ∅, after iteration i the following properties hold: (a) If i is odd and |Xi| < k′ : for any sets C ⊆ Y + i-1 and C ′ ⊆ Yi-1 \ Y + i-1 , we have ∑x∈C f (x|Xi) ≤ ∑x∈C f (e|Y <e ) 1-ϵ and ∑e∈C′ f(e|Xi) = ϵ 1-ϵ f (Y + i-1 ). (b) If i is even and |Yi| < k′ , for any set D ⊆ X+

• i-1 and D′ ⊆ Xi-1\X+ i-1 , we have ∑x∈D f (x|Yi) ≤ ∑x∈D f (e|X<e ) 1-ϵ and

Using Lemma 4 and the fact that if |T| = k, then |T \ O| ≥ |O \ T |, where T ∈ {X+, Y +}, we can bound of the optimal solution in some cases related to the size of X and Y in Lemma 5.

Lemma 5. If BoostAdapt succeeds and X1 = ∅, at the end BoostAdapt we have

Finally, putting them together, we give the tighter ratio in Theorem 6.

Theorem 6. For any ϵ ∈ (0, 1/4), BoostAdapt algorithm runs in O(log(n/ϵ) log(k/ϵ)/ϵ2 ) adaptivity, O(n log(k/ϵ)/ϵ2 ) query complexity in expectation. The algorithm succeeds with probability at least 1 - 1n , in which case it achieves a ( 14 - ϵ)-approximation ratio.

Proof. Due to the space limit, we put proof for successful probability and complexities in the appendix. If the algorithm succeeds, we now prove the ratio by considering the following cases: (1) If X1 ̸= ∅ or Y2 ̸= ∅, we have f(S) ≥ max{f(X1), f(Y2)} ≥ (1-ϵ)2 k′M 4k ≥ (1 - ϵ)2 opt 4 > ( 14 - ϵ)opt. (2) If X1 and Y2 are both empty. If |X| < k′ and |Y | < k′ , from Lemma 5, we have f(S) > (1-ϵ)2 (1-2ϵ) 4 opt > ( 1 4 - ϵ)opt. If there exists T ∈ {X, Y } such that |T | = k, then f(S) ≥ (1-ϵ)4 opt 4 > ( 14 -ϵ)opt.

7 Empirical Study

In this section, we compare our LinAst, LinAtg and BoostAdapt 1 with state-of-the-art for non-monotone SMC, including IteratedGreedy (IG) [Gupta et al., 2010], FastRandomGreedy (FRG) [Buchbinder et al., 2015], PITG[Chen et al., 2025], ParSSP[Cui et al., 2023], FASTLS+GUIDEDRG (FLS) [Chen et al., 2024a], AdaptiveSimpleThreshold (AST) [Chen and Kuhnle, 2024], and AdaptiveThresholdGreedy (ATG) [Chen and Kuhnle, 2024]. The comparison is about four metrics: object values, adaptive complexity, number of queries, and running time. We experimented with two applications: Revenue Maximization (RM) and Maximum Cut (MC) [Chen and Kuhnle, 2024; Kuhnle, 2019; Amanatidis et al., 2020]. Dataset and Setting. For all algorithms, we've fixed the parameter ϵ = 0.1. For our proposed algorithms. Each algorithm was executed over 20 independent runs, and the reported results are the average over these runs. We used Astro (n = 18, 772,m = 198, 110) for RM and utilized web-Google (n = 875, 713,m = 5, 105, 039), GrQc (n = 5, 242,m = 14, 496), and Barabasi-Albert (n = 968, m = 5, 708) for MC.

Figure 1 displays the results on the Astro and GrQC datasets. More detailed settings and results are presented in the appendix. Objective value. Figures 1(a)(e) show the objective values of algorithms. It can be observed that the Power BI Desktop PITG AST ATG BoostAdapt FLS FRG IG LinAST LinATG ParSSP

1 The source code of our algorithms is available at https://github.com/tantdhvan/AdaptIJCAI26

lines of BoostAdapt on the top while they consistently reach the highest points with every k. The top includes FLS, BoostAdapt, LinAtg, IG and AST. Both LinAst, PITG and FRG mark a little lower than BoostAdapt, followed by AST, and ParSSP. However, with small k, the gap between lines on the top seem inconsiderable. Finally, our algorithms significantly contribute to the quality of the solution. Adaptive rounds. In the MC application (Fig. 1(f)), the adaptive rounds result three distinct groups. The group with low adaptivity includes AST, LinAst, and FRG while the medium group includes IG, LinAtg, FLS, PITG and BoostAdapt. The high group is the remaining. ParSSP and ATG algorithms waste the highest number of adaptive rounds while AST hits the lowest points. With the RM instance (Fig. 1(b)), ParSSP, ATG, PITG, and IG give high numbers of adaptivities. When k increases, their quantities of the adaptive rounds seem to grow quickly, 4-10 times larger than the others. LinAtg slightly differs from the lowest AST while LinAst and BoostAdapt are higher than AST, but they do not exceed 200. Number of queries. In both RM and MC (Figures 1(c) and (g)), our algorithms almost always minimize the number of queries. In RM (Figure 1(c)), LinAst has the lowest number of queries, followed by LinAtg and BoostAdapt algorithms. The number of queries for AST is slightly higher than that of BoostAdapt. The remaining with ATG, FRG, ParSSP, FLS, PITG, and IG belong to the high-query number group. Especially, ATG and PITG mark the highest. For MC (Figure 1(g)), LinAtg reaches the lowest, followed by BoostAdapt and LinAst. The algorithms AST, ParSSP, and FRG again perform at an average level. In contrast, PITG typically requires the highest number of queries-approximately five times more than the lowest, LinAtg. On the whole, all our algorithms save queries more than the others. Moreover, our query numbers remain steady over the range of k. This is consistent with (nearly) linear query complexities of our algorithms. Time taken. In MC (Figure 1(h)), LinAst wastes the lowest time, followed by IG and FRG. While BoostAdapt, FLS, and LinAtg have the same running time, which is higher than IG and FRG but lower than AST, PITG, and ParSSP. The gap among them considerably reduces, especially when k increases, except ParSSP. Meanwhile, the time consumption of ParSSP steadily grows up along with k's growth. In RM (Figure 1(d)), LinAst and AST have the lowest running time, closely followed by the group of LinAtg, BoostAdapt, ATG. The rest spend more time than the others, especially ParSSP, which runs the slowest, about 10-20 times higher than the others. Overall, these metrics demonstrate that our algorithms consistently achieve higher-quality solutions while requiring substantially fewer queries and a small number of adaptive rounds. Compared to PITG, the strongest baseline, BoostAdapt achieves higher objective values with up to 5-7× fewer iterations and oracle queries (RM, k = 210).

8 Conclusions

Motivated by the big data challenge for non-monotone submodular maximization under cardinality constraint, we focus on parallel approximation algorithms based on the concept of adaptive complexity. In particular, we proposed efficient parallel algorithms that significantly improve both approximation ratio and query complexity but keep the near-optimal adaptive complexity of O(logn). Our algorithm also expresses superior solution quality and computation complexity compared to state-of-the-art algorithms.

Acknowledgments

Tan D. Tran was funded by the Master, PhD Scholarship Programme of Vingroup Innovation Foundation (VINIF), code VINIF.2024.TS.069.