Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

1 Introduction

In the variety of submodular optimization, Submodular Maximization under a Knapsack (SMK) constraint is one of the most fundamental problems. In this problem, given a ground set V of size n and a non-negative submodular set function f : 2V ↦→ R+. Assume that each element e ∈ V has a positive cost c(e) and there is a budget B, SMK asks for finding S ⊆ V subject to c(S) = ∑e∈S c(e) ≤ B that maximizes f(S). SMK captures important constraints in practical applications, such as bounds on costs, time, or size, thereby attracting a lot of attention recently [Mirzasoleiman et al., 2016; Amanatidis et al., 2021; Han et al., 2021; Sviridenko, 2004; Li et al., 2022; Ene and Nguyen, 2019; Lee et al., 2010a; Amanatidis et al., 2020; Gupta et al., 2010].

In addition to obtaining a near-optimal solution to SMK, designing such a solution also focuses on reducing query complexity, especially in an era of big data. With an explosion of input data, the search space for a solution has increased exponentially. Unfortunately, submodularity requires an algorithm to evaluate the objective function whenever observing an incoming element. Therefore, it is necessary to design efficient algorithms that reduce the number of queries to linear or nearly linear.

∗Corresponding author

Furthermore, to model SMK for real-world applications, the objective functions may be non-monotone, since the marginal contribution of an element to a set may not always increase. Notable examples with non-monotone objective functions can be found in revenue maximization on social network [Mirzasoleiman et al., 2016; Kuhnle, 2019], image summarization with a representative [Mirzasoleiman et al., 2016] or maximum weight cut [Amanatidis et al., 2020].

Unfortunately, no constant approximation algorithm with linear query complexity exists for non-monotone SMK compared to its counterpart. For the monotone SMK, the best approximation factor of e/(e - 1) is achieved within O(n5 ) number of queries [Sviridenko, 2004]; and the fastest algorithm has a factor of 2 + ϵ needs a linear number of queries [Li et al., 2022]. But for non-monotone, the best approximation algorithm needs polynomial queries and has a factor of 1/0.385 [Buchbinder and Feldman, 2019] and the fastest algorithm with constant factor requires near-linear query complexity of O(n log k), where k is the maximum cardinality of any feasible solution to SMK [Han et al., 2021]. Thus this work aims to close this gap by addressing the following open question: Is there a constant factor approximation algorithm for non-monotone SMK in linear query complexity?

Solving non-monotone SMK with linear query complexity is more challenging than that of the monotone case due to the following reasons. First, the property of the monotone submodular function plays an important role in analyzing the theoretical bound of an obtained solution. Second, algorithms for the non-monotone case need more queries to obtain information from all elements in the condition that the marginal contribution of an element may be negative.

Our Contributions. To tackle the above challenges, we propose two approximation algorithms, DLA and RLA, that achieve a constant factor approximation, yet both require linear query complexity. Our DLA is a deterministic algorithm with an approximation factor of 6+ϵ within O(n log(1/ϵ)/ϵ)

queries. Therefore, DLA is significantly faster than the deterministic algorithm of [Han et al., 2021], which achieved the best-known approximation factor for 6 + ϵ with nearly-linear query complexity of O(n log(k/ϵ)/ϵ). RLA is a randomized algorithm that achieves a factor of 4 + ϵ in O(n log(1/ϵ)/ϵ) queries. Therefore, RLA achieves the same factor of the randomized algorithm as in [Han et al., 2021], which currently provides the best approximation factor in near-linear query complexity of O(n log(k/ϵ)/ϵ). Note that k may be as large as n, so the query complexity of the algorithms in [Han et al., 2021] can be O(n log(n/ϵ)/ϵ). Table 1 compares the performance of our algorithms with that of existing fast algorithms.

Both our algorithms focus on a novel algorithmic approach that consists of two components: (1) dividing the ground set into two appropriate subsets and finding the approximation solution over these subsets with linear queries, and (2) combing the threshold greedy procedure developed by [Badanidiyuru and Vondr´ak, 2014] with two disjoint candidate solutions (for DLA) or a random process (for RLA) to construct serial candidate solutions to give better theoretical bounds. At the heart of the first component, we adapt the method of simultaneously constructing two disjoint sets, which is first introduced by [Han et al., 2020; Amanatidis et al., 2022] and later used by [Sun et al., 2022; Han et al., 2021] to bound the utility of candidate solutions. By incorporating a method of dividing the ground set into two reasonable subsets, we can bound the cost of feasible solutions, thereby obtaining a constant approximation factor within only a one-time scan over these subsets. In the second component, we adapt the threshold greedy, where thresholds are adjusted accordingly to provide a constant number of candidate solutions. Finally, we boost the solution quality of our algorithm by re-scanning the best elements for selecting candidate solutions without increasing query complexity.

Extensive experiments show that our algorithms outperform several state-of-the-art algorithms [Mirzasoleiman et al., 2016; Amanatidis et al., 2021; Han et al., 2021] regarding solution quality and the number of queries. In particular, DLA provides the best solution quality and needs fewer queries than the faster approximation deterministic algorithm in [Han et al., 2021], while RLA returns competitive solutions but needs the fewest queries.

Paper Organization. The rest of the paper is structured as follows. Section 2 provides the literature review on non-monotone SMK problem. Notations are presented in Section 3. Section 4 introduces our proposed algorithms and theoretical analysis. Experimental computation is provided in Section 5. Finally, we conclude this work in Section 6.

2 RelatedWorks

In this section, we review the related work for the non-monotone SMK problem only. A brief review of monotone SMK and submodular maximization subject to cardinality, a special cases of SMK, can be found in the Appendix.

Randomization is one of the effective methods for designing approximation algorithms for submodular non-monotone SMK. The first randomized algorithm was proposed by [Lee et al., 2010b] with a factor of 5 + ϵ; the factor was later improved to 4 + ϵ by [Kulik et al., 2013]. Several researchers tried to enhance the approximation factor to e/(e - 1) + ϵ or e + ϵ [Chekuri et al., 2014; Feldman et al., 2011; Ene and Nguyen, 2019; Buchbinder and Feldman, 2019]. The best factor in this line of randomized algorithms was 1/0.385 ≈ 2.6 due to [Buchbinder and Feldman, 2019], using the multi-linear extension method with the rounding scheme technique in [Kulik et al., 2013]. However, this work has to handle complicated multi-linear extensions and uses a large number of queries. In contrast, [Amanatidis et al., 2020] proposed a sample greedy, a fast algorithm with a factor of 5.83 + ϵ requiring O(n log(n/ϵ)/ϵ) queries. An efficient parallel algorithm with a factor of 9.465+ϵ was introduced by [Amanatidis et al., 2021], but it needed a high query complexity of O(n2 log2 (n) log(1/ϵ)/ϵ3 ). Significantly, [Han et al., 2021] introduced the current fastest randomized algorithm with the factor of 4 + ϵ in O(n log(k/ϵ)/ϵ) queries.

For the deterministic algorithm approach, [Gupta et al., 2010] first presented a deterministic algorithm with a factor of 6. Their algorithm modified Sviridenko's algorithm [Sviridenko, 2004] and combined with an algorithm for unconstrained non-monotone submodular maximization [Buchbinder et al., 2015]; however, it took O(n5 ) query complexity. Since then, there are several algorithms have been proposed to reduce the number of queries. The FANTOM algorithm [Mirzasoleiman et al., 2016] improved the query complexity to O(n2 log(n)/ϵ) but returned a larger factor of 10. Algorithm of [Li, 2018] achieved a factor of 9.5 + ϵ in O(nk)max{ϵ-1 , log logn} and it can be used for p-system and d-knapsack constraints. [Cui et al., 2021] introduced a streaming algorithm with a factor of 2.05 + ρAlg in O((n + TAlg(k)) logB) queries, where ρAlg was the approximation factor any offline algorithm Alg for SMK and TAlg(k) was the query complexity of Alg with k input elements. The factor and query complexity of the algorithm are quite large because they depend on ρAlg and k can be as large as n. Recently, [Han et al., 2021] also presented another one that was deterministic the factor of 6 + ϵ in nearly-linear queries O(n log(k/ϵ)/ϵ). Currently, the best approximation factor of a deterministic algorithm for non-monotone SMK is due to [Sun et al., 2022] achieving an approximation factor of 4 + ϵ but requiring an impractical query complexity of O(n3 log(n/ϵ)/ϵ).

3 Preliminaries

We use the definition of submodularity based on the diminishing return property: A set function f : 2V ↦→R+, defined on all subsets of a ground set V of size n is submodular iff for any A ⊆ B ⊆ V and e ∈ V \ B, we have:

Each element e ∈ V is assigned a positive cost c(e) > 0, and the total cost of a set S ⊆ V is a modular function, i.e., c(S) = ∑e∈S c(e). Given a budget B, we assume that every item e ∈ V satisfies c(e) ≤ B; otherwise, we can simply discard it. The SMK problem is to determine:

We denote an instance of SMK by a tuple (f, V, B). For simplicity, we assume that f is non-negative, i.e., f(X) ≥ 0 for all X ⊆ V and normalized, i.e., f(∅) = 0. We define the contribution gain of an element e to a set S ⊆ V as f (e|S) = f (S ∪ {e}) - f (S) and we write f ({e}) as f (e) for any e ∈ V . We assume that there exists an oracle query, which when queried with the set S returns the value f(S).

We denote O as an optimal solution with the optimal value opt = f(O) and r = argmaxo∈O c(o). Another frequently used property of a non-negative submodular function is: For any T ⊆ V and two disjoint subsets X, Y of V we have:

We use this Lemma to analyze our algorithms' performance.

Lemma 1. (Lemma 2.2. in [Buchbinder et al., 2014]) Let f : 2V ↦→ R+ be submodular. Denote by A(p) a random subset of A where each element appears with probability at most p (not necessary independently). Then E[f(A(p))] ≥ (1 - p)f (∅).

4 Proposed Algorithms

In this section, we introduce two main algorithms, DLA and RLA. The core of these two algorithms lies in our novel design of LA (Linear Approximation), a 19-approximation algorithm within O(n) queries. Although its factor approximation is quite large, it is the first deterministic algorithm that gives a constant approximation factor within only a linear number of queries for the general SMK problem. LA is a key building block for our DLA and its randomized version, RLA.

4.1 LA Algorithm

The LA algorithm (Algorithm 1) splits the ground set into two subsets V1 and V2. The first contains any element whose cost is at most B/2; the second includes the rest. The key strategy for LA is dividing the ground set into subsets to quickly find out the bound of the optimal solution in linear queries, then

Algorithm 1: LA Algorithm

Input: An instance (f, V, B). 1: V1 ← {e ∈ V : c(e) ≤ B/2}, X ← ∅, Y ← ∅ emax ← argmaxe∈V f(e) 2: foreach e ∈ V1 do 3: Find Z ∈ {X, Y } such that: Z = arg maxZ∈{X,Y }: f(e|Z) c(e) ≥ f(Z) B f(e|Z) c(e) 4: If exist such set Z then Z ← Z ∪ {e} 5: end 6: X′ ← argmaxX(j):0≤j≤|X|,c(X(j))≤B c(X(j)) 7: Y ′ ← argmaxY (j):0≤j≤|Y |,c(Y (j))≤B c(Y (j)), where T(j) is a set of last j elements added in T ∈ {X, Y }. 8: S ← argmaxZ∈{X′ ,Y ′ ,{emax}} f(Z) 9: return S.

selecting potential elements into two sets to get a constant approximation factor for SMK.

Since the feasible solution for over V2 contains at most one element, we can bound it by the maximal singleton emax = argmaxe∈V f(e). For the subset V1, the algorithm initiates two empty disjoint sets X, Y ; each has a threshold (ratio of f value over B) to consider the admission of a new element. A considered element is added to a set Z ∈ {X, Y } to which it has the higher ratio between marginal gain and its cost with respect to Z (i.e. "density gain") as long as the density gain is at least f(Z)/B. Note that the cost of disjoint sets may be higher than B, so we obtain feasible solutions from them by only selecting the last elements added with the cost nearest to B (lines 6-7). Finally, the algorithm returns a feasible solution with the maximum f value.

Note that the approach of [Li et al., 2022] gave a range bound of an optimal solution for the monotone SMK problem in linear time, but it does not work for the non-monotone objective function and does not provide any feasible solution. To deal with the non-monotone function, our algorithm maintains X and Y to be always disjoint and exploit (2) to get:

and bound the optimal value by f(O) ≤ f(O1) + f(O2) where O1 and O2 are optimal solutions of the problem over V1 and V2, respectively.

On the other hand, an advantage of our algorithm is that we can use the f value of the maximal singleton to design and analyze theoretical bounds for our later algorithms.

Lemma 2 provides a bound of optimal solution V1 by two disjoint sets X, Y , which is critical to analyze the theoretical bound of Algorithm 1.

Lemma 2. At the end of the main loop of Algorithm 1, we have: f(O1) ≤ 3(f(X) + f(Y )).

Theorem 1. Algorithm 1 is deterministic, returns an approximation factor of 19 and takes O(n) queries.

We further introduce the LAR (Algorithm 2) algorithm, a randomized version of Algorithm 1. LAR selects Vp from V1 by selecting e ∈ V1 with probability p > 0, then it builds the candidate set S from Vp instead of maintaining two disjoint

Algorithm 2: LAR Algorithm

Input: An instance (f, V, B), parameters p, α 1: emax ←maxe∈V f(e), V1 ← {e ∈ V |c(e) ≤ B/2} 2: Vp ← {e ∈ V1 : Select e with probability p}, S ← ∅ 3: foreach e ∈ Vp do 4: If f (e|S)/c(e) ≥ αf (S)/B then S ← S ∪ {e} 5: end 6: S′ ← argmaxS(j):0≤j≤|X|,c(X(j))≤B c(S(j)), where S(j) is a set of last j elements added into S. 7: S ← argmaxT∈{S′ ,{emax}} f(T) 8: return S.

sets. Although LAR is a randomized algorithm, it provides a better approximation factor of LA and be used for designing a later randomized algorithm RLA.

Theorem 2. Algorithm 2 takes O(n) queries and returns an approximation factor of 16.034 with p = √2 - 1 and α = √2 + 2√2.

Due to space limit, proofs of Lemmas, Theorems 1 and 2 are provided in the Appendix.

4.2 DLA Algorithm

We now introduce our DLA (Algorithm 3), a Deterministic and Linear query complexity Approximation algorithm that has an approximation factor of 6 + ϵ. The key strategy is combining the properties of two disjoint sets with a greedy threshold to construct several candidate solutions to analyze the theory of the non-monotone objective function.

DLA takes an instance (f, V,B) and a parameter ϵ as inputs. DLA consists of two phases. At the first one (lines 1-9), the algorithm calls LA as a subroutine to obtain a candidate solution S′ and get an approximate range of optimal value [Γ, 19Γ] where Γ = f(S′ ) (line 1). It then adapts the greedy threshold to add elements with high-density gain into two disjoint sets X and Y . Specifically, this phase consists of multiple iterations; each scans one time over the ground set (lines 3-9). An element added to the set T ∈ {X, Y } to which has the higher density gain without violating the budget constraint, as long as the density gain is at least θ, which initiates to 19Γ/(6ϵ′ ) and decreases by a factor of (1 - ϵ′ ) after each iteration until less than to Γ(1 - ϵ′ )/(6B), where ϵ′ = ϵ/14.

The second phase (lines 10-16) is to improve the quality of candidate solution T ∈ {X, Y } which was obtained at the end of phase 1. Denote T i as a set of the first ith elements added in T in phase 1. Our main observation is that the performance of DLA depends on the cost of T ′ = argmaxT i :c(T i )≤B-c(r)(i). Recall that r is argmaxo∈O c(o) and c(r) ≤ B. We scan an upper bound of c(T ′ ) from ϵ′B to B and improve the quality of T ′ by adding into it an element e = arg maxe∈V :c(T ′∪{e})≤B f (T ′ ∪ {e}) (lines 13-15).

The following Lemmas give the bounds of the final solution when c(r) < (1 - ϵ′ )B and c(r) ≥ (1 - ϵ′ )B, respectively.

Lemma 3. If c(r) < (1 - ϵ′ )B, one of two things happens: a) f(S) ≥ 1 6(1+ϵ′ ) opt; b) There exists a subset X′ ⊆ X so

Algorithm 3: DLA Algorithm

Input: An instance (f, V, B), ϵ > 0 1: S′ ← LA(f, V,B), Γ← f(S′ ), ϵ′ ← ϵ 14 2: ∆← ⌈ log(1/ϵ′ ) ϵ′ ⌉, θ ← 19Γ/(6ϵ′B),X ← ∅, Y ← ∅ 3: while θ ≥ Γ(1- ϵ′ )/(6B) do 4: foreach e ∈ V \ (X ∪ Y ) do 5: Find T ∈ {X, Y } such that: c(T ∪ {e}) ≤ B and T = arg maxT∈{X,Y }, f(e|T ) c(e) ≥θ f (e|T ) c(e) 6: If exist such set T then T ← T ∪ {e} 7: end 8: θ ← (1 - ϵ′ )θ 9: end 10: for l = 0 to ∆ do 11: X′(l) ← argmaxXi :c(Xi )≤ϵ′B(1+ϵ′ )l ,i≤|X| i 12: Y ′ (l) ← argmaxY i :c(Y i )≤ϵ′B(1+ϵ′ )l ,i≤|X| i 13: eX ← arg maxe∈V :c(X′ (l)∪{e})≤B f(X′(l) ∪ {e}) 14: eY ← arg maxe∈V :c(Y ′ (l)∪{e})≤B f(Y ′ (l) ∪ {e}) 15: X(l) ←X′(l) ∪ {eX}, Y(l) ← Y ′ (l) ∪ {eY } 16: end 17: S ← argmaxT∈{S′ ,X,Y,X(0),..,X(∆),Y(0),..,Y(∆)} f(T) 18: return S.

that f (O ∪ X′ ) ≤ 2f (S) + max{ 1+ϵ′ 1-ϵ′ f(S), (1-ϵ′ ) 6 opt}. Similarly, one of two conditions happens: c) f(S) ≥ 1 6(1+ϵ′ ) opt; d) There exists a subset Y ′ ⊆ Y so that f(O ∪ Y ′ ) ≤ 2f (S) + max{ 1+ϵ′ 1-ϵ′ f(S), (1-ϵ′ ) 6 opt}.

Lemma 4. If c(r) ≥ (1 - ϵ′ )B, one of two things happens: e) f(S) ≥ (1-ϵ′ )2 6 opt; f) There exists a subset X′ ⊆ X so that f (O ∪ X′ ) ≤ 2f (S) + max{ (1-ϵ′ )opt 6 , f(S) + ϵ′ opt 6 }. Similarly, one of two things happens: g) f(S) ≥ (1-ϵ′ )2 6 opt; h) There exists a subset Y ′ ⊆ Y so that f(O∪Y ′ ) ≤ 2f(S)+ max{ (1-ϵ′ )opt 6 , f(S) + ϵ′ opt 6 }.

Theorem 3. For any ϵ ∈ (0, 1), DLA is a deterministic algorithm that has a query complexity O(n log(1/ϵ)/ϵ) and returns an approximation factor of 6 + ϵ.

Proof. The query complexity of Algorithm 3 is obtained by combining the operation of Algorithm 1 and two main loops of Algorithm 3. The first and the second loops contain at most ⌈log(19/ϵ′ )/ϵ′ ⌉ + 1 and ⌈log(1/ϵ′ )/ϵ′ ⌉ iterations, respectively. Each iteration of these loops takes O(n) queries; thus we get the total number of queries at most:

To prove the factor, we consider two following cases: Case 1. If c(r) ≥ (1-ϵ′ )B. By using Lemma 4, we consider two cases: If e) or g) happens. Since ϵ′ = ϵ 14 < 1 14 we get: opt ≤ 6f(S) (1-ϵ′ )2 ≤ 6(1 + 14 13 ϵ′ )2 f(S) < (6 + ϵ)f(S), the Theorem holds. We consider the otherwise case: both e) and h) happen. There exist X′ ⊆ X, Y ′ ⊆ Y and X′ ∩ Y ′ = ∅

We consider two sub-cases: If f(S) ≥ opt 6 , the Theorem holds. If f(S) < opt 6 , put it back into (3) we get:

Case 2. If c(r) < (1 - ϵ′ )B. By applying the Lemma 3, we consider two cases: If a) or c) happens, we get f(S) ≥ opt 6(1+ϵ′ ) ⇒ opt ≤ (6 + 6ϵ′ )f(S) and the Theorem holds. If both b) and d) happen. There exist X′ ⊆ X, Y ′ ⊆ Y and X′∩Y ′ = ∅ satisfying: opt = f(O) ≤ f(O∪X′ )+f(O∪Y ′ )

If f(S) ≥ opt 6 , the Theorem is true. We consider the case f(S) < opt 6 , put it into (4) we get opt < 4f(S) + 1+ϵ′ 1-ϵ′ opt 3 . ⇒ opt < 6(1-ϵ′ ) 1-2ϵ′ f(S) = (6 + 6ϵ′

4.3 RLA Algorithm

We further introduce the RLA (Algorithm 4), a Randomized and Linear query complexity Approximation algorithm with the factor of 4 + ϵ. RLA re-uses the algorithmic framework of DLA algorithm with some modifications. In particular, we combine the threshold greedy method with a random process to construct a series of candidate solutions Sj .

Specifically, the first phase of the algorithm consists of a loop (lines 2-11) with at most ⌈log(4/ϵ′ )/ϵ′ ⌉ iterations, and each takes one pass over the ground set, where ϵ′ = ϵ/10. This loop simultaneously constructs a candidate set U = {u1, . . . , uj} and a solution Sj as follows: Each element e, not in the current candidate set, having the density gain at least θ, is added into the candidate set and then added into Sj+1 with probability 1/2. The set U plays an important role to the RLA's performance. In the second phase of this algorithm, we boost the quality of candidate solution Sj by using the same strategy with the DLA (lines 12-16).

We now analyze the performance of RLA. Considering the end of the algorithm, we first define the following notations: For any ui ∈ U = {u1, u2, . . . , uj}, define τ(ui) = i, S<ui = Si-1; for any e ∈ V \ U, τ(e) = +∞. Denote T = j, if c(Sj-1 ∪ {uj}) ≤ B - c(r). Otherwise, T = min{i : 0 ≤ i ≤ j - 1, c(Si ∪ {ui+1}) > B - c(r)}. Lemma 5 provides an efficient tool to estimate f(Si) for all i ≤ j that is helpful to obtain RLA's performance guarantee.

Algorithm 4: RLA Algorithm

Input: An instance (f, V, B), ϵ > 0 1: S′ ← LAR(f, V,B, p = √2-1, α = √2+2√2), Sj ← ∅, j ← 0, Γ ← f(S′ ), θ ← 16.034·Γ 4ϵ′B , ϵ′ ← ϵ 10 2: while θ ≥ Γ(1- ϵ′ )/(4B) do 3: foreach e ∈ V \ {u1, u2, . . . , uj} do 4: if f(e|Sj) c(e) ≥ θ and c(Sj) + c(e) ≤ B then 5: uj ← e; 6: With probability 1/2 do: Sj+1 ← Sj ∪ {e} otherwise Sj+1 ← Sj 7: j ← j +1 8: end 9: end 10: θ ← (1 - ϵ′ )θ 11: end 12: for l = 0 to ⌈log(1/ϵ′ )/ϵ′ ⌉ do 13: S′(l) ← argmaxSi:c(Si)≤ϵ′B(1+ϵ′ )l ,i≤|S| i 14: elmax ← arg maxe∈V :c(S′(l)∪{e})≤B f (S′(l) ∪ {e}) 15: S(l) ←S′(l) ∪ {elmax } 16: end 17: S ← argmaxX∈{S′ ,Sj,S(0),...,S(⌈log(1/ϵ′)/ϵ′⌉) } f(X) 18: return S.

Proof. The query complexity of RLA is obtained by the same argument in the proof of Theorem 3. Denote by θi θ at the iteration i, by θ(i) θ when ui is added into U, and θlast is θ at the last iteration of the first loop. For the approximation factor, we consider the following cases:

Case 1. If c(r) > (1 - ϵ′ )B, c(O \ {r}) < B - (1 - ϵ′ )B = ϵ′B. We consider two following sub-cases: Case 1.1. If c(Sj) ≥ (1 - ϵ′ )B, then f(S) ≥ f(Sj) ≥ c(Sj)(1 - ϵ′ ) opt 4 ≥ (1 - ϵ′ )2 opt 4 . Since ϵ′ = ϵ 10 < 1 10 , we have: opt ≤ 4f(S) (1-ϵ′ )2 ≤ 4(1+ 10 9 ϵ′ )2 f(S) ≤ (4+ϵ)f(S). Case 1.2. If c(Sj) < (1-ϵ′ )B, c(Sj)+c(e) ≤ c(Sj)+c(O\{r}) < B for all e ∈ (O\{r})\Sj. Thus f(e|Sj) c(e) < (1-ϵ′ )Γ 4B ≤ (1-ϵ′ )opt 4B .

Since each element in V appears in Sj with probability 1/2, applying Lemma 1 gives E[f (O \ {r} ∪ Sj )] ≥ 12 f (O \ {r}). Combine this with (5), we have: f(O) ≤ f(O \ {r}) + f(r) ≤ 2E[f (O \ {r} ∪ Sj )] + f (emax) < 3E[f (S)] + ϵ′ (1-ϵ′ )opt 2 .

Case 2. If c(r) ≤ (1 - ϵ′ )B, c(O \ {r}) ≥ ϵ′B. Considering the following sub-cases: Case 2.1. If T = j, by the definition of T we have: O>T = ∅. Therefore

where (6) due to f(e|S<e ) > 0, ∀e ∈ Sj and Xe is defined in Lemma 5. By applying Lemma 1 again, we have E[f(O ∪ ST )] ≥ f(O)/2. Combine this with (7), we attain

Case 2.2. If T < j, U contains at least T +1 elements and we have c(ST ) + c(uT+1) > B - c(r) > ϵ′B. We now consider the second loop of the Algorithm 3. Since ϵ′B < B - c(r) ≤ B, there exists an integer number l that:

Assuming that S′(l) = Si for some i. By selection rule of S′(l) we have c(Si) ≤ (1 + ϵ′ )l ϵ′B < c(Si ∪ {ui+1}) thus c(Si ∪ {ui+1}) > ϵ′B 1+ϵ′ . We further consider two sub-cases. If ui+1 is considered at the first iteration of the first loop, by the selection rule of elmax at the second loop, we get: f(S(l)) ≥ f(Si ∪ {ui+1}) ≥ c(Si ∪ {ui+1})θ1 ≥ opt 4(1+ϵ′ )2 . Hence, opt ≤ 4(1 + ϵ′ )2 f (S) < (4 + ϵ)f (S).

If ui+1 is considered at the lth iteration, l ≥ 2. Let ˆ S = Si \ (O \ {r}) and ˆO = O≤i \ (Si ∪ {r}). We show that

thus (8) is true. On the other hand, for any element e ∈ O>i \ {r}, its density gain with respect to Si is smaller than the threshold at the previous iteration (in the first loop), i.e., f (e|Si) c(e) ≤ θ(i+1) 1-ϵ′ . Combine this with (8), we obtain:

where (9) due to the reason that f(e|S<e )

where Ye is defined in Lemma 5. From (10) and by applying Lemma 5, we have:

By combining all cases, we attain the proof.

5 Experimental Evaluation

In this section, we compare the performance between our algorithms and state-of-the-art algorithms for the SMK problem on three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut.

5.1 Applications And Datasets

Revenue Maximization. Given a social network that represented by a graph G = (V,E) where V and represent a set of users a set of user connections, respectively Each edge (u, v) assigned a weight w(u,v) that reflects the "closeness" of u and v. We follow [Mirzasoleiman et al., 2016] to define the advertising revenue of any node set S ⊆ V as f(S) = ∑u∈V \S √∑v∈S:(v,u)∈E w(u,v). The weight w(u,v) is randomly sampled from the continuous uniform distribution U(0, 1) as in and each node u has a cost c(u) = g(√∑(u,v)∈E w(u,v)) where g(x) = 1 - e-µx and µ = 0.2 [Han et al., 2021]. Given a budget of B, the goal of the problem is to select a set S with the cost at most B to maximize f(S). This problem is an instance of non-monotone SMK [Han et al., 2021]. In this application, we utilized the egoFacebook dataset from [Leskovec et al., 2007] which consists of over 4K nodes and over 88K edges.

Image Summarization. Given a graph G = (V , E) where each node u ∈ V represents an image, and each edge (u, v) ∈ E is assigned a weight wu,v representing the similarity between image u and image v. Define c(u) the cost to collect the image u. The goal is to identify a representative subset S ⊆ V with a limited budget B that maximizes the representative value defined as f(S) = ∑u∈V maxv∈S wu,v - 1 |V | ∑u∈V ∑v∈S wu,v [Mirzasoleiman et al., 2016; Han et al., 2021]. The function f(·) is non-monotone, non-negative, and submodular [Mirzasoleiman et al., 2016]. Following the recent work [Han et al., 2021; Mirzasoleiman et al., 2016], we set this instance as follows: We first randomly selected 500 images from the CIFAR data sets [Krizhevsky, 2019; Mirzasoleiman et al., 2016], which contained 10.000 images. We then measure the similarity between image u and image v by using the cosine similarity of their 3.072-dimensional pixel vectors. Finally, we use Root Mean Square (RMS) contrast as a metric to evaluate the quality of the images and assign a cost to each image based on its RMS contrast.

MaximumWeighted Cut. Given a graph G = (V,E), and a non-negative edge weight wu,v for each (u, v) ∈ E. For a set of nodes S ⊂ V , define the weighted cut function f(S) = ∑u∈V \S ∑v∈S wu,v . The maximum (weighted) cut problem is to find a subset S ⊆ V such that the f(S) is maximized. It is indicated in [Kuhnle, 2019; Amanatidis et al., 2020] as f(·) is non-monotone and submodular. The datasets used in the application included an Erd˝os-R´enyi (ER) random graph with 5000 nodes, and an edge probability of 0.2 and the cost of each node c(u) was randomly uniformly chosen from the range (0, 1) as in [Amanatidis et al., 2020].

Experiment Settings. We compare our algorithms with the applicable state-of-the-art algorithms listed below:

• FANTOM: The randomized algorithm of [Mirzasoleiman et al., 2016] with the expected factor of the 10 + ϵ in O(n2 log(n)/ϵ).
• SAMPLE GREEDY: The randomized algorithm of [Amanatidis et al., 2020] with the factor 5.83 + ϵ in query complexity of O(n log(n/ϵ)/ϵ) queries. For the easy following, we refer to SAMPLE GREEDY as the GREEDY.
• SMKDETACC: The deterministic algorithm of [Han et al., 2021] with the factor 6 + ϵ in O(n log(k/ϵ)/ϵ) queries. This is the fastest deterministic approximation algorithm for non-monotone SMK.
• SMKRANACC: This is the fastest randomized algorithm of [Han et al., 2021] with the expected approximation factor 4+ϵ in query complexity of O(n log(k/ϵ)/ϵ).
• SMKSTREAM: The first streaming algorithm for studied problem that returns the approximation factor of 6+ϵ within O(n log(B)/ϵ) queries [Han et al., 2021].

In our experiments, the budget range from 2% to 12% of the total cost of the ground sets as setting of [Amanatidis et al., 2020]. We set ϵ = 0.1 for all algorithms and α = β = 1/6, h = 2, r = 2 for SMKSTREAM [Han et al., 2021].

5.2 Experiment Results

The result of the experiment is shown in Figure 1. First, Figures 1(a)(c)(e) represent the quality of algorithms via values of the objective function on 3 instances. As can be seen, DLA always gives the highest values at all B milestones in all instances. RLA, SMKRANACC, and SMKSTREAM are not much different. FANTOM results lower while GREEDY provides the lowest. Regarding the deterministic algorithm, DLA is several tens to thousands of units better than SMKDETACC on (a) and (e), especially, several times higher on (c). Regarding the randomized algorithm, our RLA gives as well quality as SMKRANACC. This result insists that our algorithm ensures good performance compared to the algorithms of [Han et al., 2021], which are currently the best. In the end, our algorithm tends to be considerably better than the rest when B's values increase.

Figures 1(b)(d)(f) illustrate the number of queries of the above algorithms. FANTOM is the highest, SMKSTREAM is the second, and the remaining is much lower. FANTOM and SMKSTREAM require millions of queries, whereas the rest is thousands of times lower than them. In the rest, the GREEDY's queries are also usually higher than the others except on (f). Queries of DLA, RLA, and SMKRANACC look similar while queries of SMKDETACC change due to different datasets. RLA spends the fewest queries, and DLA needs fewer queries than that of SMKDETACC. When B grows, the number of queries of RLA increases slowest, whereas the queries of SMKDETACC increase fastest. Especially, in Image Summarization, DLA, RLA, SMKDETACC, and SMKRANACC are all approximately 2K at B = 2% the total cost; however, SMKDETACC is 5 times higher than the rest when B = 12%.

On the whole, our algorithms, DLA, and RLA keep the balance between performance guarantee and query complexity. It's extremely important to save running time with big data. Moreover, experimental results show that our algorithms are efficient ones comparable to state-of-the-art algorithms.

6 Conclusions

Motivated by the challenge of solving the non-monotone SMK on the massive data, in this work, we proposed two approximation algorithms DLA, RLA. To the best of our knowledge, our algorithms are the first to achieve a constant factor approximation for the considered problem in linear query complexity. Our algorithms' superiority in solution quality and computation complexity compared to state-of-the-art algorithms was supported by the experiment results in three real-world applications.

Acknowledgements

This work was supported in part by the National Science Foundation (NSF) grants IIS-1908594.