Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint

1 Introduction

Maximizing classes of set functions, generalizing submodular functions, has emerged recently due to its wide range applications in real-world problems. Among those works, nonsubmodular maximization subject to cardinality constraint was studied the most extensively, including but not limited to [Bian et al., 2017; Das and Kempe, 2011; Qian et al., 2018; Kuhnle et al., 2018].

However, cardinality constraint may not be sufficient to capture some natural requirements of various applications. For example, in many viral marketing campaigns, it is important to ensure the diversity and fairness among different ethnics and genders. These applications aim to distribute budget to feed information fairly among different groups of users while guaranteeing to maximize the influence spread in the network. Another example is data summarization. In many situations, a large data may be formed by elements of various classes. The problem, thus, aims to find a representative subset to cover the dataset's content as much as possible while imposing a constraint that the subset should contain a number of members of each class to guarantee diversity.

Motivated by those observation, we study the following problem: Given a ground set V , a non-negative monotone function f : 2V → R≥; let V1, ..., Vk be a collection of disjoint subsets forming V (i.e. V = V1 ⊎ ... ⊎ Vk), and b1, ..., bk be k integers that 1 ≤ bi ≤ |Vi| ∀i ∈ [k]. The problem asks for:

MAXMP is formally represented as monotone nonsubmodular maximization with partition matroid constraint. This constraint is a special case of matroid constraint and generalizes cardinality constraint.

Non-submodular maximization beyond cardinality constraint has only received attention recently. The most recent works are [Chen et al., 2018] and [Gatmiry and GomezRodriguez, 2018], in which they studied the performance guarantee of GREEDY or RESIDUAL GREEDY (RESGREEDY) [Buchbinder et al., 2014] on monotone non-submodular maximization subject to matroid constraint. However, those algorithms requires O(nK) queries of f (K is a rank of a matroid), which may not be desirable in practice. Researchers [Mirzasoleiman et al., 2016; Badanidiyuru and Vondr´ak, 2014; Kuhnle et al., 2018] have sought ways to speed up the GREEDY algorithm. Unfortunately, these approaches were only for cardinality constraint; or relied upon the submodularity of f.

To our knowledge, there exists no specific work dedicating for non-submodular maximization subject to partition matroid constraint. That leaves us open questions on: (1) With partition matroid, does there exist an algorithm with a better ratio or can we improve the ratio of the existing algorithms, whose performance guarantees have been proven with a matroid constraint? (As partition matroid is a special case of matroid constraint, perhaps we can get a tighter ratio if we only considered the partition matroid.) (2) Can we leverage partition matroid properties to devise approximation algorithms with more query-efficient?

In this work, we focus on answering the above two questions. First, to quantify the non-submodularity of a function, we introduce Partition Matroid Curvature α and Partition Matroid Diminishing-Return ratio γ. These two quantities are derived from the same concept with the diminishing-return ratio [Lehmann et al., 2006; Bogunovic et al., 2017] and generalized curvature [Bian et al., 2017; Conforti and Cornu´ejols, 1984; Iyer et al., 2013] but have more relaxed requirements.

Our main contribution is to introduce a novel approximation algorithm, named PROB, with approximation ratio of (1/γ ′ - 1 + α′ )(1 - 1/Θ(maxi∈[k] |Vi|)) + 1 where γ ′ and α′ are non-trivial and obtainable bounds of γ and α. PROB's novelty lies in a random process of selecting a new element, in which the algorithm introduces a new probability distribution among non-selected elements. That probability distribution is a key for PROB to obtain its ratio. Furthermore, by utilizing a sampling technique to reduce searching space, we propose FASTPROB, an algorithm improving from PROB with efficient query complexity of O(n ln2 ∑i∈[k] bi).

Furthermore, we re-investigate theoretical performance guarantees of two existing techniques, GREEDY and THRESHOLD GREEDY (THRGREEDY). We proved that: with partition matroid constraint, GREEDY can obtain a ratio of min (α/(1 - (1 - αγ/ ∑i∈[k] bi)mini∈[k] bi ), (1 + γα)/γ ), which - in comparing with existing work of [Friedrich et al., 2019] in matroid constraint - has its own advantage in some certain range of non-submodular quantification parameters.

Finally, we investigate our algorithms' performance on two applications of MAXMP: Boosting Influence Spread and Video Summarization. We provide bounds on the objective functions' partition matroid curvature and diminishing ratio to have a better insight on theoretical guarantees of our algorithms. Experimental results show our algorithms return comparable solutions to the state-of-the-art techniques while totally outperform them in the number of queries.

2 RelatedWork

2.1 Quantifying Non-Submodularity

To bound how close a function to submodularity, three most popular quantities in literature are: (1) weakly submodular ratio; (2) diminishing return ratio; and (3) generalized curvature. Weakly submodular ratio, denoted as γs, was first introduced by [Das and Kempe, 2011] and further used by [Elenberg et al., 2017; Qian et al., 2015; Chen et al., 2018]. γs is defined as the maximum value in range [0, 1] such that f(S ∪ T) - f(S) ≤ 1 γs ∑e∈T\S (f(S ∪ {e}) - f(S)) for all S, T ⊆ V . Diminishing-return (DR) ratio γd [Bogunovic et al., 2018; Lehmann et al., 2006; Qian et al., 2018; Kuhnle et al., 2018] is defined as the largest value in range [0, 1] that guarantees f(T ∪{e})-f(T) ≤ 1 γd (f (S ∪ {e}) -

f(S)) for all S ⊆ T ⊆ V and e ̸∈ T. γd was proven to be at most the value of γs [Kuhnle et al., 2018]. General curvature αc [Bian et al., 2017; Conforti and Cornu´ejols, 1984; Iyer et al., 2013], on another hand, is the smallest number in [0, 1] that f(T ∪{e})-f(T) ≥ (1-αc)(f(S∪{e})-f(S)).

In this work, we adapt DR-ratio and curvature but with more relaxed requirements. To be specific, instead of requiring those quantities to be applicable for all sets, we narrow down the collection of subsets S ⊆ T that need to satisfy those properties to |(T \ S) ∩ Vi| ≤ bi for all i ∈ [k]. If considering size constraint, this relaxation is corresponding to the definition of Greedy DR-ratio and Greedy Curvature [Bian et al., 2017; Kuhnle et al., 2018]. Not only this relaxation is sufficient to bound our approximation ratios; but it also helps us obtain meaningful bounds of those quantities in the MAXMP's applications in our experiments.

2.2 Beyond Cardinality Constraint

Non-submodular maximization beyond cardinality constraint has received attention recently. [Chen et al., 2018] was the first one who brought up the concept of non-submodular maximization subject to matroid constraint. In this work, the authors proved that RESGREEDY can obtain the ratio of (1 + 1 γs )2 . [Gatmiry and Gomez-Rodriguez, 2018] then proved GREEDY is able to obtain a ratio of √γsK+1 0.4γ 2 s and 1+1/γd.

In submodular maximization, the study beyond cardinality constraint is too extensive to give a comprehensive overview. Due to space limit, we only go over representative works; and refer readers to a comprehensive discussion in [Calinescu et al., 2011; Buchbinder et al., 2019; Friedrich et al., 2019].

For decades, GREEDY- with ratio of 2 [Cornnejols et al., 1977] - has been considered as the best algorithm for monotone submodular maximization subject to matroid constraint. This was up until [Calinescu et al., 2011] introduced a concept of multilinear extension of submodular functions to devise a 1/(1 - 1/e) algorithm. However, their expensive complexity remains a significant bottleneck to make the algorithm be applicable; and improving it is still an intriguing open question for future research. The newest breakthrough is of [Buchbinder et al., 2019], who devised an algorithm, namely SPLITGROW, with a ratio of 1/0.5008 and ˜O(nK2 +KT) complexity - where T is the complexity to find a maximum weight perfect matching in a bipartite graph with 2K vertices.

The most recent work on partition matroid, to our knowledge, is of [Friedrich et al., 2019], in which the authors proved GREEDY is able to obtain a ratio of αc/(1 - exp [ - αc mini∈[k] bi ∑i∈[k] bi ]). We generalizes this work to non-submodular objective function by providing analysis that GREEDY can obtain a ratio of min (α/(1 - (1 - αγ/ ∑i∈[k] bi)mini∈[k] bi ), 1/γ +α). If only considering submodular objective function, our ratio has an advantage that it is bounded by 1/γ + α. Therefore, its ratio does not degrade when the input is formed by many partitions.

We also provide approximation ratio of THRGREEDY. THRGREEDY has been studied by [Kuhnle et al., 2018] for the problem of monotone non-submodular maximization with cardinality constraint. Since partition matroid generalizes cardinality constraint, our analysis techniques are totally different to [Kuhnle et al., 2018]. If projecting our ratio to cardinality constraint, our ratio is better than the one of [Kuhnle et al., 2018], which is 1/(1 - e-γdγs(1-ϵ) - ϵ). The keys help us obtain a better ratio are (1) γs is not necessary to bound inequality between obtained solutions and the optimal solution; and (2) we utilizes the general curvature to tighten the inequality equations, thus our ratio becomes better if the curvature moves away from the trivial value 1.

3 Definitions and Notations

Given a set function f, a set S and e ̸∈ S, denote ∆ef(S) := f (S ∪ {e}) - f (S).

Given the partition matroid constraint of MAXMP, including V = V1 ⊎ ... ⊎ Vk and b1, ..., bk, denote b = ∑i∈[k] bi; n = |V |; ni = |Vi| ∀i ∈ [k]. Let ¯n = maxi∈[k] ni and ˆb = mini∈[k] bi. A set S ⊆ V is called a maximal set to the constraint iff |S ∩ Vi| = bi ∀i ∈ [k].

Definition 1. Given an instance of MAXMP, including

Algorithm 1 PROB

Return Sb

V = V1 ⊎ ... ⊎ Vk; {b1, ..., bk} and f . The Partition Matroid (PM) Diminishing Return ratio γ of the objective function f is defined as the maximum value in [0, 1] that guarantees ∆ef(T) ≤ 1 γ ∆ef(S) for any S ⊆ T that |(T \ S) ∩ Vi| ≤ bi ∀i ∈ [k] and e ∈ V \ T .

Definition 2. Given an instance of MAXMP, including V = V1 ⊎ ... ⊎ Vk; {b1, ..., bk} and f . The Partition Matroid (PM) Curvature α of the objective function f is defined as the minimum value in [0, 1] that guarantees ∆ef (T ) ≥ (1-α)∆ef (S) for any S ⊆ T that |(T \S)∩Vi| ≤ bi ∀i ∈ [k] and e ∈ V \T .

It is unknown in the literature on how hard it is to obtain exact values of quantities quantifying non-submodularity. γ and α are not exceptional either. Fortunately, for some applications, we can obtain non-trivial bounds of γ and α, which can help assess approximation ratios of our algorithms. We denote γ ′ as a lower bound of γ, e.g. γ ≥ γ ′ ≥ 0; and α′ as a upper bound of α, e.g. α ≤ α′ ≤ 1.

W.l.o.g, we assume the objective function f is normalized, i.e. f(∅) = 0, and bi ≤ ni for all i ∈ [k]. In our algorithms' analysis, we denote S∗ as an optimal solution, i.e f(S∗ ) = maxS:|S∩Vi|≤bi f(S).

4 PROB and FASTPROB Algorithms

4.1 PROB Algorithm

PROB is a randomized algorithm with approximation ratio of (1/γ ′ - 1 + α′ )(1 - 1/O(¯n)) + 1. Pseudocode of PROB is presented by Alg. 1. In general, PROB works in rounds, and at each round, one member of a group Vi is added to the obtained solution S if |S ∩ Vi| < bi. The key for PROB to obtain efficient performance guarantee lies in a random process, which introduces a probability distribution, defined locally for each group, to select a new element of each group to add into the obtained solution (line 6 Alg. 1). This random process allows us to construct a sequence of maximal sets in order to form a recursive relationship among changes on the f's values of the obtained solutions, which is critical to bound PROB's approximation ratio.

Theorem 1. PROB obtains a ( 1 γ ′ + α′ - 1)(1 - 1 ¯n+2 ) + 1-approximation solution and has query complexity of O(∑i∈[k] nibi).

Proof. Denote β = ( 1 γ ′ +α′ -1)(1- 1 ¯n+2 ) and S1, ..., Sb as a sequence of obtained solution by PROB. We prove the approximation ratio of PROB by constructing a sequence of maximal sets S∗ 0 , ..., S ∗ b that satisfies the following properties: (1) S∗ 0 = S∗ and S∗ b = Sb; (2) St ⊂ S∗ t for all t = 0, ..., b-1 and Sb = S∗ b ; (3) f(S∗ t )-f(S∗ t+1 ) ≤ β E[f (St+1) - f (St)] for t = 0 → b - 1. Then, we have:

To construct the sequence, starting with S∗ 0 = S∗ , for each t = 1, ..., b-1, S∗ t+1 is formed fromS∗ t , St and et as follows: Let i be the index being considered at the for loop (line 3 Alg. 1); and et will be added into St. Since St ⊂ S∗ t and |St ∩ Vi| < bi, (S∗ t \ St) ∩ Vi ̸= ∅. Let e′ be any arbitrary element in (S∗ t \ St) ∩ Vi. S∗ t+1 is set as follows:

• If et ∈ (S∗ t \ St) ∩ Vi, S∗ t+1 := S∗ t .

Denote ρe = ∆ef(St) and Pre = ρae ∑v∈Vi\St ρav (i.e. Pre is probability e is selected). We have:

where Equ. (4) is from properties of γ and α; while Equ. (7) is from AM-GM inequality.

Replacing a = ⌈ |Vi\St|+1 1-γ ′ (1-α′ ) ⌉ - 1, we have

Therefore, combining Equ. (10), (12) to (8), we have:

The query complexity of PROB can be trivially inferred from the algorithm's pseudocode.

Due to differences in definition of the quantities quantifying non-submodularity and how algorithms' ratios depend on them, it is no clear way to compare their ratios. For example, RESGREEDY obtains (1+ 1 γs )2 -ratio [Chen et al., 2018]. Although γs ≥ γ ≥ γ ′ , it is unclear how this ratio is compared with PROB's ratio. However, PROB has a better query complexity than RESGREEDY (O(nb)).

When f is submodular (γ = 1), PROB can obtain a ratio of 1+α′ (1- 1 ¯n+2 ). Although PROB's ratio is still not comparable to the best ratio (1 - 1/e) of [Calinescu et al., 2011], their expensive complexity O(n8 ) remains a significant bottleneck to make their algorithm be applicable in practice. In compare with the most recent work [Buchbinder et al., 2019], PROB can reach a better ratio than SPLITGROW ( 1 0.5008 ) with appropriate values of α′ and ¯n; and PROB has much better query complexity than SPLITGROW (O(nb2 )).

4.2 FASTPROB Algorithm

PROB's query complexity can be improved by observing that the proof of Theorem 2 can non-trivially go through if et is selected from a set that overlaps with (S∗ t \ St) ∩ Vi for all t = 1, ..., b. This always works in Alg. 1 since et is selected from Vi \ St. Therefore, we can use sampling to reduce the space of selecting et as in Alg. 2.

We call Alg. 2 FASTPROB. The condition which helps FASTPROB has the same ratio as PROB with probability at least 1 - δ, is guaranteed as stated in the following lemma.

Lemma 1. (S∗ t \ St) ∩ Rt ̸= ∅ for all t = 0, ..., b - 1 with probability at least 1- δ

Proof. We prove for each t = 0, ..., b-1, Pr[(S∗ t \St)∩Rt = ∅] ≤ δb . Then using union bound, (S∗ t \ St) ∩Rt ̸= ∅ for all t = 0, ..., b-1 with probability at least 1-δ. This probability is trivial if Rt = Vi \ St. If |Rt| = ni-|St∩Vi| bi-|St∩Vi| ln b δ , since St ⊆ S∗ t , |(S∗ t \ St) ∩ Vi| = bi - |St ∩ Vi|. We have:

which completes the proof.

Algorithm 2 FASTPROB

Return Sb

Theorem2. FASTPROB obtains a ( 1 γ ′ +α′-1)(1- 1 ¯n+2 )+1approximation solution with probability at least 1 - δ and has query complexity of O(n ln b ln b δ ).

Proof. The method to prove FASTPROB's approximation ratio is similar to the proof of PROB. Due to space limit and for the sake of completeness, we provide the proof of FASTPROB's ratio in Appendix [Nguyen and Thai, 2022].

In term of query complexity, it is trivial that the number of queries of FASTPROB is ∑b-1 t=0 |Rt|. We have:

where Equ. (16) is from the fact that logx is a concave function, so ∑i αi logxi ≤ logαixi if ∑i αi = 1; and ∑i∈[k] nibi n ≤ ∑i∈[k] ni n ∑i∈[k] bi = b.

5 GREEDY-like Algorithms

We re-study the theoretical performance guarantee of two algorithms, GREEDY and THRGREEDY. Our analysis provides better ratios of GREEDY than existing works on matroid constraint [Gatmiry and Gomez-Rodriguez, 2018] or submodular objective function [Friedrich et al., 2019].

In general, GREEDY works in round and at each round, an element of maximal marginal gain, whose addition does not violate partition matroid constraint, is added to the obtained solution. The algorithm terminates when the obtained solution

Algorithm 3 GREEDY

Input V = V1 ⊎ ... ⊎ Vk; f ; b1, ..., bk

• 1: I = [k]; S0 = ∅; t = 0
• 2: while I ̸= ∅ do
• 3: e, i = argmaxe∈Vi\St;i∈I ∆ef(St)
• 4: St+1 = St ∪ {e}; t = t +1
• 5: if |St ∩ Vi| ≥ bi then I = I \ {i}

Return Sb

is maximal. THRGREEDY, on the other hand, works by always keeping a threshold τ , which bounds the maximum marginal gain to the objective by any non-selected elements. The algorithm runs in rounds; at each round, any element with a marginal gain at least τ will be added to the solution if it does not violate the partition matroid constraint. After each round, τ is decreased by a factor 1 - ϵ in order to guarantee new elements can be added to the solution at successive rounds. The algorithm continues until the obtained solution becoming a maximal set or the threshold is below a value defined by ϵ and b. GREEDY's pseudocode is presented by Alg. 3 and THRGREEDY's is Alg. 4.

Theorem 3. GREEDY obtains a min( 1 r(g) 1 , 1 r(g) 2 )- approximation solution, where

and has a query complexity of O(n b).

Theorem 4. THRGREEDY obtains a min( 1 r(t) 1 , 1 r(t) 2 )- approximation solution, where

and has a query complexity of O( nϵ lnb).

Due to space limit, full proofs of Theorem 3 and 4 is provided in Appendix [Nguyen and Thai, 2022].

In case of submodular objective function, r(g) 2 of GREEDY is identical to the ratio obtained by [Friedrich et al., 2019]. With cardinality constraint, r(g) 2 matches with the ratio of [Bian et al., 2017], which was also proven to be tight. However, with ˆb/b → 0 (e.g. the input is formed by many partitions), r(g) 2 and r(t) 2 approach 0 and become undesirable. In this case, r(g) 1 and r(t) 1 should be a better bound on the performance of GREEDY and THRGREEDY.

6 Applications and Experimental Results

In this section, we consider two applications of MAXMP: Boosting Influence Spread and Video Summarization.

6.1 Applications' Formulation and Bounded Non-Submodularity Quantities

In Boosting Influence Spread, a social directed graph G = (V,E) is given, where V represents a set of social network

Algorithm 4 THRGREEDY

Input V = V1 ⊎ ... ⊎ Vk; f ; b1, ..., bk; ϵ ∈ [0, 1]

1: I = [k]; S0 = ∅; t = 0 2: τ = τ0 =maxe∈V ∆ef(S0) 3: while I ̸= ∅ and τ ≥ ϵ(1-ϵ)τ0 b do 4: for each i ∈ I and e ∈ Vi \ St do 5: if ∆ef(St) ≥ τ then 6: St+1 = St ∪ {e}; t = t + 1 7: if |St ∩ Vi| ≥ bi then I = I \ {i} 8: τ = τ(1 - ϵ)

Return St

users; and E represents friendship between social users in V . An information will start spreading at a set I ⊂ V of users. The problem asks for a set S of users to strengthen the influence spread in order to maximize the number of users whom the information can reach to.

Boosting Influence Spread under size constraint has been studied by [Lin et al., 2017]. In their model, each edge e = (u, v) ∈ E is associated with two weight values p0e , p1e (p0e ≤ p1e ≤ 1). The probability v adopts the information from u is p1e if v ∈ S; p0e otherwise. In this application, f(S) measures expected number of users the information can reach if S is selected. The authors has proven that f is monotone nonsubmodular; but did not show how close f is to submodularity. We provide the bound γ ′ , α′ of γ and α of f as in Lemma 2, and full proof is provided in [Nguyen and Thai, 2022].

Lemma 2. Given a Boosting Influence Spread instance, let ∆ be the maximum in-degree of the input directed graph. For any S ⊆ T that |(T \ S) ∩ Vi| ≤ bi ∀i ∈ [k] and u ∈ V \ T :

With Video Summarization, given a video, the problem aims to pick a few representative frames from the video which can contains as much content as possible. The video contains n frames; each frame is represented by a p-dimensional vector. Let X ∈ Rn×n be the Gramian matrix of the n resulting vectors and the Gaussian kernel; i.e. Xij is the value of the Gaussian kernel between the i-th and j-th vectors. The objective function is defined as f(S) = det(I +XS), where XS is the submatrix of X indexed by S; and I is a unit matrix.

f(S) was proved to be supermodular by [Bian et al., 2017], thus its curvature α = 0. The authors also bounded the weakly submodular ratio, which is not useful in our algorithms. We bound the value of γ as in the following lemma, and full proof is provided in Appendix [Nguyen and Thai, 2022].

Lemma 3. Given a Video Summarization instance, let A = I +X and λi(M) be the i-th eigenvalue of a positive definite matrix M in a way that λ1(M) ≥ ... ≥ λrank(M) (M). For any S ⊆ T that |(T \ S) ∩ Vi| ≤ bi ∀i ∈ [k] and e ∈ V \ T :

6.2 Settings and Compared Algorithms

With Boosting Influence Spread, we use Facebook dataset from SNAP database [Leskovec and Krevl, 2014], an undirected graph with 4,039 nodes and 88,234 edges. Since it is undirected, we treat each edge as two directed edges. For each edge e = (u, v), p0e = 1 dv and p1e = 2 dv where dv is in-degree of v. Information starts spreading at a node of highest degree. Due to lack of information, a user is randomly assigned to a group Vi. The budget is distributed equally to each group, i.e. b1 ≈ ... ≈ bk ≈ bk . The objective is estimated over 100 pre-sampled graph realizations of G.

With Video Summarization, we chose a video of roughly 3.5 minutes. The video is segmented to k equal-length parts; and the algorithms will pick bk frames from each part.

With FASTPROB, we set δ = 0.001, which guarantees FASTPROB to return solutions almost similar to PROB but be much better in the number of queries. With THRGREEDY, we set ϵ = 0.5. Results were averaged over 10 repetitions.

We varied values of b and k; and compare FASTPROB, GREEDY and THRGREEDY with RESGREEDY [Chen et al., 2018] and SPLITGROW [Buchbinder et al., 2019]. Although SPLITGROW's performance is unknown if f is submodular, we used it as a heuristic to compare.

6.3 Numerical Results

Fig. 1 and 2 show experimental results of different algorithms on Boosting Influence Spread and Video Summarization. With experiments that we varied values of b, we fixed k = 2. With the one that k is varied, we fixed b = 100 in Boosting Influence Spread and b = 20 in Video Summarization.

In these experiments, FASTPROB, GREEDY and SPLITGROW performed approximately equal in term of solution quality while THRGREEDY was always the worst one. Especially, in Video Summarization, the supermodular objective function made the marginal gain of non-included elements increase with larger obtained solutions. Therefore, THRGREEDY easily reached a maximal solution just by one or two iterations of decreasing threshold. That explained why THRGREEDY took very few number of queries but has undesirable returned solution quality. In term of the number of queries, FASTPROB outperformed GREEDY, RESGREEDY and SPLITGROW.

FASTPROB closed the gap or even surpassed THRGREEDY to become the best algorithm in the number of queries in the experiments with fixed b and varied k. In these experiments, we can see that the number of queries of all algorithms, except FASTPROB, almost did not change or just slightly decreased with larger k. FASTPROB's numbers, on the other hand, decreased significantly as k increased. This phenomenon is also reflected on the theoretical bound of FASTPROB's complexity. In Equ. (15), FASTPROB's complexity is bounded by O(ln b δ ∑i∈[k] ni ln bi). With nis are roughly equal (the same with bis), FASTPROB's complexity becomes O(n ln bk ln b δ ), which decreases w.r.t k.

7 Discussion

We proposed PROB and later FASTPROB to solve monotone non-submodular maximization with partition matroid constraint. The experimental results demonstrated that FASTPROB can perform closely to the best algorithms in solution quality, and outperform other algorithms (except THRGREEDY- the worst in solution quality) in the number of queries. Although there is no superior algorithm in general, FASTPROB should be considered as the best algorithm in scenarios that scalability issues are concerned, e.g. algorithms with fast runtime and relatively high solution quality.

There is still an open question on what is the best algorithm in approximation ratio? PROB's ratio depends on γ ′ , α′ - which can be undesirable in some settings of our experiments. However, how hard to obtain exact value of γ, α or other non-submodular quantities is unknown. And computing those quantities by enumerating all possible S, T that T \ S satisfies partition matroid is too expensive. Therefore, the differences between GREEDY, THRGREEDY, RESGREEDY and PROB's ratio are still remained open.

Acknowledgements

This work was supported in part by the National Science Foundation (NSF) grants IIS-1908594 and IIS-1939725. We'd like to thank the anonymous reviewers for their helpful feedback.