Paper deep dive
Data-dependent Evaluations for Budgeted Submodular Maximization
Lejian Zhang, Xueyan Tang, Jing Tang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 7/8/2026, 3:06:42 AM
Summary
This paper addresses the NP-hard problem of Monotone Submodular Maximization with a Knapsack constraint (MSMK). It introduces novel data-dependent upper bounds to evaluate how close algorithmic solutions are to the optimal solution for specific problem instances. The authors propose two derivation strategies—a slicing strategy and a removing strategy—which are transformed into linear programs. Theoretical proofs demonstrate that these bounds strictly dominate the optimal solution and are tighter than existing methods. Empirical evaluations on real-world datasets, including maximum coverage, revenue maximization, and feature selection, validate the effectiveness of the proposed bounds in certifying solution quality.
Entities (10)
Relation Signals (12)
Xueyan Tang → authored → Data-dependent Evaluations for Budgeted Submodular Maximization
confidence 99% · Data-dependent Evaluations for Budgeted Submodular Maximization Lejian Zhang1, Xueyan Tang1, and Jing Tang2
Jing Tang → authored → Data-dependent Evaluations for Budgeted Submodular Maximization
confidence 99% · Data-dependent Evaluations for Budgeted Submodular Maximization Lejian Zhang1, Xueyan Tang1, and Jing Tang2
Lejian Zhang → authored → Data-dependent Evaluations for Budgeted Submodular Maximization
confidence 99% · Data-dependent Evaluations for Budgeted Submodular Maximization Lejian Zhang1, Xueyan Tang1, and Jing Tang2
Data-dependent upper bounds → appliedto → Monotone Submodular Maximization with a Knapsack constraint (MSMK)
confidence 95% · we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint.
Data-dependent Evaluations for Budgeted Submodular Maximization → proposes → Data-dependent upper bounds
confidence 95% · In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint.
Data-dependent upper bounds → dominates → Optimal solution value
confidence 94% · We theoretically prove that they dominate the optimal solution
Data-dependent upper bounds → derivedvia → Removing strategy
confidence 92% · We develop two strategies, a slicing strategy and a removing strategy, to derive data-dependent upper bounds.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.
Tags
Links
- Source: https://arxiv.org/abs/2607.05759v1
- Canonical: https://arxiv.org/abs/2607.05759v1
Trouble viewing inline? Open PDF directly →
Full Text
79,630 characters extracted from source content.
Expand or collapse full text
Data-dependent Evaluations for Budgeted Submodular Maximization Lejian Zhang1, Xueyan Tang1, and Jing Tang2 1 College of Computing and Data Science, Nanyang Technological University, Singapore 2 Data Science and Analytics Thrust, The Hong Kong University of Science and Technology (Guangzhou), China lejian001@e.ntu.edu.sg, asxytang@ntu.edu.sg, jingtang@ust.hk Abstract Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets. 1 Introduction A great number of optimization problems in different areas can be modeled as submodular maximization problems, including facility location [21], feature selection [8], recommendation system [18], influence maximization [26], document summarization [20], maximum coverage [10], sensor placement [16], exemplar sampling [12] and market expansion [9]. Due to the NP-hard nature of submodular maximization, many approximation algorithms have been developed, attempting to find good solutions in polynomial time. Approximation algorithms are typically evaluated by the approximation factor, which refers to the worst-case ratio between the function value of an output solution and that of an optimal solution. Nemhauser and Wolsey [22] introduced a simple greedy algorithm which guarantees an approximation factor of 1−1/e1-1/e for the problem of Monotone Submodular Maximization with a Cardinality constraint (MSMC) (finding a set S of a given size which maximizes f(S)f(S)). But the greedy algorithm does not guarantee any positive approximation factor for the more general problem of Monotone Submodular Maximization with a Knapsack constraint (MSMK) (finding a set S of total cost at most a given budget which maximizes f(S)f(S), assuming elements have costs). Wolsey [27] improved the simple greedy algorithm by a small modification and showed that it achieves an approximation factor of 0.357. Khuller et al. [15] attempted to derive an approximation factor of 1−1/e≈0.3931-1/ e≈ 0.393 for the modified greedy algorithm, but their analysis was found flawed [29]. Tang et al. [25] proved that this modified greedy algorithm actually guarantees an approximation factor of 0.405. Subsequently, more careful approximation analysis showed that the exact approximation factor of the modified greedy algorithm is between 0.427 and 0.42945 [11, 17]. Both the simple and modified greedy algorithms run in O(n2)O(n^2) time, where n is the size of the ground set. Sviridenko [24] proposed a (1−1/e)(1-1/e)-approximation algorithm at the expense of increasing the time complexity to O(n5)O(n^5). The time complexity of the algorithm was later reduced to O(n4)O(n^4) without sacrificing the approximation factor [11, 17]. Yaroslavtsev et al. [28] developed a 0.50.5-approximation algorithm called Greedy+Max that runs in O(n2)O(n^2) time. Feldman et al. [11] augmented Greedy+Max with a single guess to achieve an approximation factor of 0.61740.6174 in O(n3)O(n^3) running time. The running times of these algorithms can be reduced from O(ni)O(n^i) to O~(ni−1/ϵ) O(n^i-1/ε) (ignoring poly-logarithmic terms) at the cost of losing an ϵε in the approximation factors using the threshold technique of [2]. Although the above algorithms provide approximation factors, these constant factors usually leave a significant gap between the solution obtained and the optimal solution of a particular problem instance because they consider only the worst-case scenarios. It is challenging to measure how close to optimal an output solution is for a specific problem instance in practice. One possible method is to derive upper bounds on the optimal function values on a per-instance basis. We refer to such bounds as data-dependent bounds. Unlike the constant approximation factors which are fixed and independent of problem instances, data-dependent bounds can be used to characterize the actual quality of the solutions constructed on different problem instances in an instance-aware manner. Recently, a few studies have attempted this method. Balkanski et al. [3] and Chakrabarty and Cote [7] introduced instance-specific upper bounds for the MSMC problem, but these bounds cannot be applied to the MSMK problem directly. Tang et al. [25] presented a naive data-dependent upper bound for the MSMK problem. In this paper, we construct and evaluate new data-dependent upper bounds on the optimal solution for the MSMK problem. Our contributions can be summarized as follows: • We develop two strategies, a slicing strategy and a removing strategy, to derive data-dependent upper bounds. We theoretically prove that the constructed bounds dominate the optimal solution, and they are tighter than the existing bounds. • We transform these strategies into linear programs so that multiple base sets can be incorporated into the derivation of data-dependent upper bounds, which further tightens the established bounds. • We conduct extensive experiments with several real-world applications, including maximum coverage, revenue maximization, and feature selection, to demonstrate empirically the advantages of our proposed bounds in certifying the quality of solutions to the MSMK problem. The rest of this paper is organized as follows. Section 2 gives a formal definition of the MSMK problem and some preliminaries. Section 3 elaborates the design and analysis of our data-dependent upper bounds. Section 4 discusses the experiments. Finally, Section 5 concludes the paper. 2 Preliminaries Given a ground set V, a set function f:2V→ℝf 2^V is submodular if for any two sets A,B⊆VA,B V, it holds that f(A)+f(B)≥f(A∩B)+f(A∪B).f(A)+f(B)≥ f(A∩ B)+f(A∪ B). An equivalent definition of a submodular set function f is that for any two sets A⊆B⊆VA B V and any element v∈V∖Bv∈ V B, it holds that f(A∪v)−f(A)≥f(B∪v)−f(B).f(A∪\v\)-f(A)≥ f(B∪\v\)-f(B). The latter definition describes the diminishing return property of a submodular set function. In this paper, we focus on monotone submodular maximization, where a set function f is monotone (non-decreasing) if f(A)≤f(B)f(A)≤ f(B) for any two sets A⊆B⊆VA B V. The input to the MSMK problem includes a ground set V, a non-negative monotone submodular set function f:2V→ℝ≥0f:2^V _≥ 0, a non-negative modular cost function c:2V→ℝ≥0c:2^V _≥ 0 to measure the cost of selecting elements (where c(S)=∑v∈Sc(v)c(S)= _v∈ Sc(v) and c(v)c(v) is the cost of element v), and a budget b. The objective of the MSMK problem is to find a set that maximizes the function value f among all the sets of cost at most b, i.e., argmaxS⊆V,c(S)≤bf(S) _S V,\,c(S)≤ bf(S). Without loss of generality, we assume that for each element v∈Vv∈ V, c(v)≤bc(v)≤ b. We define the marginal gain of an element v with respect to a set S as fS(v)=f(S∪v)−f(S)f_S(v)=f(S∪\v\)-f(S), i.e., the increase in the function value by adding v to S. We define the marginal density of an element v with respect to a set S as dS(v)=fS(v)c(v)d_S(v)= f_S(v)c(v), i.e., the marginal gain normalized by the element cost. Due to the diminishing return property of a submodular set function, the marginal gain and density of an element v are the highest when S=∅S= and are the lowest when S=V∖vS=V \v\ (among the sets S that do not contain v). We refer to the marginal density in the latter case, i.e., dV∖v(v)d_V \v\(v), as the cutoff density. For notational convenience, we shall use fS(T)f_S(T) to denote the marginal gain of a set T with respect to another set S, i.e., fS(T)=f(S∪T)−f(S)f_S(T)=f(S∪ T)-f(S). Let OPTOPT denote an optimal solution to the MSMK problem. For any set S⊆VS V, we have f(OPT) f(OPT) =f(OPT∪S)−fOPT(S) =f(OPT∪ S)-f_OPT(S) =f(S)+fS(OPT)−fOPT(S) =f(S)+f_S(OPT)-f_OPT(S) ≤f(S)+maxT⊆V,c(T)≤b(fS(T)−fT(S)) ≤ f(S)+ _T V,\,c(T)≤ b(f_S(T)-f_T(S)) ≤f(S)+maxT⊆V,c(T)≤bfS(T), ≤ f(S)+ _T V,\,c(T)≤ bf_S(T), (1) where the first inequality follows from the fact that c(OPT)≤bc(OPT)≤ b. Our main approach is to construct an upper bound Λ(S) (S) on the last term maxT⊆V,c(T)≤b(fS(T)−fT(S)) _T V,\,c(T)≤ b(f_S(T)-f_T(S)) or maxT⊆V,c(T)≤bfS(T) _T V,\,c(T)≤ bf_S(T) in Section 2. Given any set S⊆VS V, we can then derive an upper bound on f(OPT)f(OPT) by computing f(S)+Λ(S)f(S)+ (S), where S will be termed the base set. Technically, we develop two strategies: a slicing strategy that constructs an upper bound on maxT⊆V,c(T)≤bfS(T) _T V,\,c(T)≤ bf_S(T), and a removing strategy that derives an upper bound on maxT⊆V,c(T)≤b(fS(T)−fT(S)) _T V,\,c(T)≤ b(f_S(T)-f_T(S)) from an upper bound on maxT⊆V,c(T)≤bfS(T) _T V,\,c(T)≤ bf_S(T). We further transform these strategies into linear programs to facilitate dealing with multiple base sets. For simplicity of presentation, we define the ground set V:=1,2,…,nV:=\1,2,…,n\. Without loss of generality, we assume that S=1,2,…,pS=\1,2,…,p\ when discussing a base set S⊆VS V. In addition, we also assume that the elements in S are arranged in non-descending order of cutoff density, i.e., dV∖1(1)≤dV∖2(2)≤⋯≤dV∖p(p)d_V \1\(1)≤ d_V \2\(2)≤·s≤ d_V \p\(p). The elements in the remaining set V∖SV S are arranged in non-ascending order of marginal density with respect to S, i.e., dS(p+1)≥dS(p+2)≥⋯≥dS(n)d_S(p+1)≥ d_S(p+2)≥·s≥ d_S(n). 3 Design and analysis of upper bounds 3.1 Removing strategy It is easy to infer that maxT⊆V,c(T)≤bfS(T)=maxT⊆V∖S,c(T)≤bfS(T) _T V,\,c(T)≤ bf_S(T)= _T V S,\,c(T)≤ bf_S(T), because T should include only elements from V∖SV S in order to maximize the marginal gain fS(T)f_S(T). To construct an upper bound on maxT⊆V∖S,c(T)≤bfS(T) _T V S,\,c(T)≤ bf_S(T), an intuitive idea is to find the lowest index r in the remaining set V∖S=p+1,p+2,…,nV S=\p+1,p+2,…,n\ satisfying ∑i=p+1rc(i)>b _i=p+1^rc(i)>b [25]. The upper bound is defined as follows: Λ0(S)=∑i=p+1r−1fS(i)+(b−∑i=p+1r−1c(i))⋅dS(r). ^0(S)= _i=p+1^r-1f_S(i)+ (b- _i=p+1^r-1c(i) )· d_S(r). (2) In essence, Λ0 ^0 takes elements in the remaining set greedily according to their marginal density with respect to the base set S until the budget b is fulfilled. Owing to the submodularity of f, it is easy to see that Λ0(S) ^0(S) is an upper bound on maxT⊆V∖S,c(T)≤bfS(T)=maxT⊆V,c(T)≤bfS(T) _T V S,\,c(T)≤ bf_S(T)= _T V,\,c(T)≤ bf_S(T). Given a base set S, the time complexity to compute Λ0(S) ^0(S) is O(nlogn)=O(|V|log|V|)O(n n)=O(|V| |V|) due to the sorting of the elements. By Section 2, f(S)+Λ0(S)f(S)+ ^0(S) gives an upper bound on f(OPT)f(OPT). Nevertheless, it “consumes” a total cost of b+c(S)b+c(S). On the other hand, it is impossible for an optimal solution to spend any cost exceeding the budget b. We would like to tighten Λ0 ^0 by removing some elements and make the total cost equal to b, i.e., to construct an upper bound on maxT⊆V,c(T)≤b(fS(T)−fT(S)) _T V,c(T)≤ b(f_S(T)-f_T(S)). We start by defining a continuous version of the marginal gain function with respect to S based on the remaining set V∖S=p+1,p+2,…,nV S=\p+1,p+2,…,n\: G+(x)=∑i=p+1r−1fS(i)+(x−∑i=p+1r−1c(i))⋅dS(r),G_+(x)= _i=p+1^r-1f_S(i)+ (x- _i=p+1^r-1c(i) )· d_S(r), (3) where r is the lowest index satisfying ∑i=p+1rc(i)>x _i=p+1^rc(i)>x. Note that Λ0(S)=G+(b) ^0(S)=G_+(b). G+(x)G_+(x) calculates an upper bound on the marginal gain generated by selecting elements from V∖SV S with a total cost of x, i.e., for any T⊆V∖ST V S, G+(c(T))≥∑i∈TfS(i)≥fS(T).G_+(c(T))≥ _i∈ Tf_S(i)≥ f_S(T). (4) Obviously, G+(x)G_+(x) is non-decreasing. Intuitively, we would like to pick G+(b−c(S))G_+(b-c(S)) to fill up the budget b. However, G+(b−c(S))G_+(b-c(S)) is not necessarily an upper bound on fS(OPT∖S)f_S(OPT S), because we cannot guarantee that c(OPT∖S)≤b−c(S)c(OPT S)≤ b-c(S). We propose to first choose elements to consume a total cost of b+xb+x and then remove elements from S to reduce the total cost to b. To do so, we define another continuous function G−(x)G_-(x) to calculate a lower bound on the loss in the function value f caused by removing elements with a total cost of x. Function G−(x)G_-(x) is defined as: G−(x) G_-(x) =∑i=1s−1fV∖i(i)+(x−∑i=1s−1c(i))⋅dV∖s(s), = _i=1^s-1f_V \i\(i)+ (x- _i=1^s-1c(i) )· d_V \s\(s), (5) where s is the lowest index in S=1,2,…,pS=\1,2,…,p\ satisfying ∑i=1sc(i)>x _i=1^sc(i)>x. That is, G−(x)G_-(x) takes elements greedily according to their cutoff density until an accumulated cost x is reached. Clearly, G−(x)G_-(x) is also non-decreasing. It is easy to see that for any set T⊆S∖OPT S OPT, we have G−(c(T))≤∑i∈TfV∖i(i)≤fV∖T(T)≤fOPT(T),G_-(c(T))≤ _i∈ Tf_V \i\(i)≤ f_V T(T)≤ f_OPT(T), where the first inequality is by the definition of G−(x)G_-(x) and the last two inequalities are due to the submodularity of f. To maintain a total cost equal to b, if G+(b−c(S)+x)G_+(b-c(S)+x) is picked, we can remove G−(x)G_-(x) from it. Ideally, we would like to set x∗=maxc(OPT∪S)−b,0.x = \c(OPT∪ S)-b,0\. Then, it holds that b−c(S)+x∗≥b−c(S)+c(OPT∪S)−b=c(OPT∪S)−c(S)b-c(S)+x ≥ b-c(S)+c(OPT∪ S)-b=c(OPT∪ S)-c(S) and x∗≤c(OPT∪S)−c(OPT)x ≤ c(OPT∪ S)-c(OPT). Hence, we have G+(b−c(S)+x∗)−G−(x∗) G_+(b-c(S)+x )-G_-(x ) ≥G+(c(OPT∪S)−c(S))−G−(c(OPT∪S)−c(OPT)) ≥ G_+(c(OPT∪ S)-c(S))-G_-(c(OPT∪ S)-c(OPT)) =G+(c(OPT∖S))−G−(c(S∖OPT)) =G_+(c(OPT S))-G_-(c(S OPT)) ≥fS(OPT∖S)−fOPT(S∖OPT) ≥ f_S(OPT S)-f_OPT(S OPT) =f(OPT)−f(S). =f(OPT)-f(S). However, c(OPT∪S)c(OPT∪ S) is not known as it is dependent on the optimal solution OPTOPT. Note that x∗≤maxc(OPT)+c(S)−b,0≤c(S)x ≤ \c(OPT)+c(S)-b,0\≤ c(S) always holds. Thus, we can pick the maximal value of G+(b−c(S)+x)−G−(x)G_+(b-c(S)+x)-G_-(x) among all x∈[0,c(S)]x∈[0,c(S)]. Hence, an upper bound incorporating the removing strategy is defined as Λ1(S)=maxx∈[0,c(S)]G+(b−c(S)+x)−G−(x). ^1(S)= _x∈[0,c(S)] \G_+(b-c(S)+x)-G_-(x) \. Since G+(x)G_+(x) is a non-decreasing function, we have Λ0(S) ^0(S) =G+(b)≥maxx∈[0,c(S)]G+(b−c(S)+x) =G_+(b)≥ _x∈[0,c(S)]G_+(b-c(S)+x) ≥maxx∈[0,c(S)](G+(b−c(S)+x)−G−(x))=Λ1(S), ≥ _x∈[0,c(S)](G_+(b-c(S)+x)-G_-(x))= ^1(S), which shows that Λ1 ^1 is at least as good as Λ0 ^0. 3.1.1 Λ1 ^1 in linear program presentation We can also present the calculation of Λ1 ^1 as a linear program shown in Equation 6, where ⟨x1,x2,…,xn⟩∈[0,1]n x_1,x_2,…,x_n ∈[0,1]^n is an indicator vector.111All linear programs in this paper will have variables x1,x2,…,xnx_1,x_2,…,x_n forming an indicator vector. We shall omit the constraint ∀i∈V, 0≤xi≤1∀ i∈ V,\,0≤ x_i≤ 1 in the presentations of linear programs for conciseness. max ∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi) _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i) (6) subject to ∑i∈Vc(i)⋅xi≤b. _i∈ Vc(i)· x_i≤ b. We prove the equivalence between the optimum of Equation 6 and Λ1(S) ^1(S) in Appendix A. According to Equation 6, we can arrange elements in V in descending order according to their “weights” in the objective function. That is, for each i∈Si∈ S, its weight is fV∖i(i)f_V \i\(i); for each i∈V∖Si∈ V S, its weight is fS(i)f_S(i). We can then pick elements greedily from the beginning and stop when the budget is fulfilled. Given a set S, the time complexity to compute Λ1(S) ^1(S) is O(nlogn)=O(|V|log|V|)O(n n)=O(|V| |V|) due to the sorting of the elements. Thus, Λ1(S) ^1(S) has the same time complexity to compute as Λ0(S) ^0(S). Similarly, we can also write the calculation of Λ0 ^0 as a linear program shown in Equation 7. max ∑i∈V∖SfS(i)⋅xi _i∈ V Sf_S(i)· x_i (7) subject to ∑i∈Vc(i)⋅xi≤b. _i∈ Vc(i)· x_i≤ b. Notice that Equation 6 differs from Equation 7 in only one item: −∑i∈SfV∖i(i)⋅(1−xi)- _i∈ Sf_V \i\(i)·(1-x_i). We refer to this item as the “removing item”, which is in essence the core of the removing strategy. 3.2 Slicing strategy We develop a slicing strategy to derive a data-dependent upper bound for the MSMK problem, which is inspired by Balkanski et al.’s work [3]. Their method upper bounds the optimal MSMC solution by lower bounding the dual objective of finding the set S of minimum size that has a given function value. We introduce it from a different perspective to motivate our approach to deal with the MSMK problem. Recall that the remaining set V∖S=p+1,p+2,…,nV S=\p+1,p+2,…,n\ is sorted in non-ascending order of marginal density (or equivalently marginal gain in the case of MSMC) with respect to S. To simplify presentation, we define Vi:=1,2,…,iV_i:=\1,2,…,i\ and V0:=∅V_0:= . Let k be the cardinality constraint. If the upper bound Λ0 ^0 is applied, we pick the top k elements p+1,p+2,…,p+kp+1,p+2,…,p+k from V∖SV S which have the largest marginal densities with respect to S. Now we arrange the elements in OPT∖SOPT S in non-ascending order of marginal density with respect to S and obtain a sorted sequence ⟨o1,o2,…,ok⟩ o_1,o_2,…,o_k where o1<o2<⋯<oko_1<o_2<·s<o_k. Similarly, we define Oi:=o1,o2,…,oiO_i:=\o_1,o_2,…,o_i\ and O0:=∅O_0:= . Let us first notice two properties of ⟨o1,o2,…,ok⟩ o_1,o_2,…,o_k as follows: • for each i∈1,2,…,ki∈\1,2,…,k\, fS∪Oi−1(oi)≤fS(oi)f_S∪ O_i-1(o_i)≤ f_S(o_i), which is due to the submodularity of f; • for each i∈1,2,…,ki∈\1,2,…,k\, fS∪Oi−1(oi)=fS(Oi)−fS(Oi−1)≤fS(p+1,p+2,…,oi)−∑j=1i−1fS∪Oj−1(oj)=fS(Voi)−∑j=1i−1fS∪Oj−1(oj)f_S∪ O_i-1(o_i)=f_S(O_i)-f_S(O_i-1)≤ f_S(\p+1,p+2,…,o_i\)- _j=1^i-1f_S∪ O_j-1(o_j)=f_S(V_o_i)- _j=1^i-1f_S∪ O_j-1(o_j), which is due to the monotonicity of f. Balkanski et al.’s method [3] replaces each fS∪Oi−1(oi)f_S∪ O_i-1(o_i) with a variable viv_i. Each variable viv_i corresponds to a distinct element in V∖SV S because oio_i can be any element in V∖SV S. It then maximizes the total value of the sequence v1,v2,…,vkv_1,v_2,…,v_k satisfying the above conditions. Since fS(o1),fS∪O1(o2),…,fS∪Ok−1(ok)f_S(o_1),f_S∪ O_1(o_2),…,f_S∪ O_k-1(o_k) is also such a sequence satisfying these conditions, the maximum total value of v1,v2,…,vkv_1,v_2,…,v_k is an upper bound for it. Thus, ∑i=1kvi≥∑i=1kfS∪Oi−1(oi)=fS(OPT∖S) _i=1^kv_i≥ _i=1^kf_S∪ O_i-1(o_i)=f_S(OPT S), and f(S)+∑i=1kvif(S)+ _i=1^kv_i is an upper bound on f(OPT)f(OPT). The elements picked by this method do not necessarily have successive indexes. Hence, it produces an upper bound at least as good as (no larger than) Λ0 ^0. Remember that we would like to construct an upper bound on maxT⊆V,c(T)≤bfS(T)=maxT⊆V∖S,c(T)≤bfS(T) _T V,\,c(T)≤ bf_S(T)= _T V S,\,c(T)≤ bf_S(T) for the MSMK problem. The main challenge of MSMK is that the elements have non-uniform costs so that the number of elements to pick and fill up the budget b is not predetermined. A naive approach to address it is to choose a fixed value ϵε and divide the budget b into slices of cost ϵε each, as illustrated in Figure 2. Then, to fill up the budget b, we pick bϵ bε slices. However, the element costs are not necessarily multiples of ϵε. Hence, it is possible for a slice to involve a number of elements, where the number is not fixed and the first as well as last elements may be partially involved. Note that all the elements involved in a slice would have successive indexes. In general, it would not guarantee that the maximum total value of all slices is an upper bound on fS(OPT∖S)f_S(OPT S), because the elements in OPT∖SOPT S may not have successive indexes. To address this issue, we can choose ϵ→0ε→ 0 so that each slice would involve only one element and thus share the same marginal density with the element it belongs to. The drawback is that setting ϵ→0ε→ 0 would increase the number of slices to pick towards infinity and hence may significantly increase the time complexity of computing the upper bound. To guarantee efficiency, we can pick all the slices belonging to the same element at once. Motivated by these thoughts, we present a novel and elegant design to construct an upper bound Λ2 ^2 for the MSMK problem. We start by defining the concept of a valid partition for the MSMK problem. Definition 1. Given a budget b and a set S, a sequence of values v1,v2,…,vn∈ℝ≥0v_1,v_2,…,v_n _≥ 0 form a valid partition of a value v∈ℝ≥0v _≥ 0 with respect to S if (i) ∑i=1nvi=v _i=1^nv_i=v; and there exists a sequence of costs s1,s2,…,sn∈ℝ≥0s_1,s_2,…,s_n _≥ 0 where si≤c(i)s_i≤ c(i) represents the cost spent on element i such that (i) ∑i=1nsi≤b _i=1^ns_i≤ b; (i) for each i∈1,2,…,ni∈\1,2,…,n\, dS(i)⋅si=fS(i)c(i)⋅si≥vid_S(i)· s_i= f_S(i)c(i)· s_i≥ v_i; (iv) for each i∈1,2,…,ni∈\1,2,…,n\, fS(Vi)≥∑j=1ivjf_S(V_i)≥ _j=1^iv_j. Figure 1: Naive slicing strategy Figure 2: Slicing strategy producing Λ2 ^2 In Definition 1, sis_i can be interpreted as the total cost of the slices we pick involving element i, as illustrated in Figure 2. Condition (i) states that the total cost of all the slices picked is capped by b. Note that for each element i∈Si∈ S, dS(i)=0d_S(i)=0. By condition (i), we always have vi=0v_i=0 for each i∈1,2,…,pi∈\1,2,…,p\. First, we prove the following property. Lemma 2. For any set T⊆V∖ST V S with c(T)≤bc(T)≤ b, fS(T)f_S(T) has a valid partition with respect to S. Proof Sketch. We construct a valid partition of fS(T)f_S(T) to prove this lemma. Please refer to Appendix B for details. ∎ Lemma 2 implies that the maximum value that has a valid partition with respect to S is an upper bound on maxT⊆V∖S,c(T)≤bfS(T) _T V S,\,c(T)≤ bf_S(T). We remark that Definition 1 and Lemma 2 actually do not require the remaining set V∖S=p+1,p+2,…,nV S=\p+1,p+2,…,n\ to be sorted in non-ascending order of marginal density with respect to S. On the other hand, having V∖SV S sorted allows us to develop an efficient algorithm to compute the maximum value that has a valid partition. To find this maximum value, for each element i∈V∖Si∈ V S, we would like to spend as little cost sis_i as possible while maximizing viv_i. By conditions (i) and (iv) of Definition 1, in general, the cost to spend on each element aia_i should be si=dS∪Vi−1(i)dS(i)⋅c(i)s_i= d_S∪ V_i-1(i)d_S(i)· c(i), so that the increase from fS(Vi−1)f_S(V_i-1) to fS(Vi)f_S(V_i) is the same as dS(i)⋅sid_S(i)· s_i. Thus, we iterate through the sorted sequence ⟨p+1,p+2,…,n⟩ p+1,p+2,...,n until encountering an element t where the remaining budget b−∑i=p+1t−1dS∪Vi−1(i)dS(i)⋅c(i)≤dS∪Vt−1(t)dS(t)⋅c(t)b- _i=p+1^t-1 d_S∪ V_i-1(i)d_S(i)· c(i)≤ d_S∪ V_t-1(t)d_S(t)· c(t). For each element i (p+1≤i<t)(p+1≤ i<t), a cost of si=dS∪Vi−1(i)dS(i)⋅c(i)s_i= d_S∪ V_i-1(i)d_S(i)· c(i) is spent on i and we set vi=dS(i)⋅si=fS∪Vi−1(i)v_i=d_S(i)· s_i=f_S∪ V_i-1(i). For the element t, a cost of st=b−∑i=p+1t−1dS∪Vi−1(i)dS(i)⋅c(i)s_t=b- _i=p+1^t-1 d_S∪ V_i-1(i)d_S(i)· c(i) is spent on t and we set vt=dS(t)⋅stv_t=d_S(t)· s_t. For all the remaining elements i (1≤i≤p1≤ i≤ p or t+1≤i≤nt+1≤ i≤ n), we set si=0s_i=0 and vi=0v_i=0. Then, we define Λ2(S)=∑i=1nvi=∑i=p+1tvi=fS(Vt−1)+(b−∑i=p+1t−1dS∪Vi−1(i)dS(i)⋅c(i))⋅dS(t). ^2(S)= _i=1^nv_i= _i=p+1^tv_i=f_S(V_t-1)+ (b- _i=p+1^t-1 d_S∪ V_i-1(i)d_S(i)· c(i) )· d_S(t). (8) The idea of constructing Λ2 ^2 is illustrated in Figure 2. Given a set S, the time complexity to compute Λ2(S) ^2(S) is O(nlogn)=O(|V|log|V|)O(n n)=O(|V| |V|) due to the sorting of the elements. Obviously, Λ2(S) ^2(S) has a valid partition as demonstrated by the cost and value sequences above. Next, we prove that Λ2(S) ^2(S) is the maximum v that has a valid partition and hence an upper bound on maxT⊆V∖S,c(T)≤bfS(T)=maxT⊆V,c(T)≤bfS(T) _T V S,\,c(T)≤ bf_S(T)= _T V,\,c(T)≤ bf_S(T). Notice that Λ2(S)=∑i=p+1tvi=∑i=p+1tdS(i)⋅si ^2(S)= _i=p+1^tv_i= _i=p+1^td_S(i)· s_i. Since dS(p+1)≥dS(p+2)≥⋯≥dS(n)d_S(p+1)≥ d_S(p+2)≥·s≥ d_S(n) and ∑i=p+1tsi=b _i=p+1^ts_i=b, we have ∑i=p+1tdS(i)⋅si≤∑i=p+1r−1dS(i)⋅c(i)+(b−∑i=p+1r−1c(i))⋅dS(r)=Λ0(S) _i=p+1^td_S(i)· s_i≤ _i=p+1^r-1d_S(i)· c(i)+ (b- _i=p+1^r-1c(i) )· d_S(r)= ^0(S), where r is the lowest index satisfying ∑i=p+1rc(i)>b _i=p+1^rc(i)>b as defined in Equation 2. This implies that Λ2(S)≤Λ0(S) ^2(S)≤ ^0(S) and hence, Λ2 ^2 is at least as good as Λ0 ^0. Lemma 3. The maximum value v that has a valid partition is given by Λ2(S) ^2(S). Proof Sketch. Let the cost sequence generated for computing Λ2(S) ^2(S) be s1,s2,…,sns_1,s_2,…,s_n and the corresponding value sequence be v1,v2,…,vnv_1,v_2,…,v_n. If s1,s2,…,sns_1,s_2,…,s_n do not use up the budget b, the claim is straightforward since ∑i=1nvi=∑i=1nfS∪Vi−1(i)=fS(Vn) _i=1^nv_i= _i=1^nf_S∪ V_i-1(i)=f_S(V_n) must be the maximum possible due to property (iv) of Definition 1 (by setting i=ni=n). Now assume that ∑i=1nsi=b _i=1^ns_i=b. We prove the lemma by contradiction. Let v~ v be the maximum value that has a valid partition and its cost sequence be s~1,s~2,…,s~n s_1, s_2,…, s_n. Assume that v~>Λ2(S) v> ^2(S). We check the difference between the two sequences and find the lowest-indexed element aqa_q where sq≠s~qs_q≠ s_q. We then derive contradictions for the cases of s~q>sq s_q>s_q and s~q<sq s_q<s_q respectively to complete the proof. Please refer to Appendix C for details. ∎ 3.2.1 Λ2 ^2 in linear program presentation Like Λ1 ^1, we can write the calculation of Λ2 ^2 as a linear program shown in Equation 9. max ∑i∈V∖SfS(i)⋅xi _i∈ V Sf_S(i)· x_i (9) subject to ∀i∈V,∑j=1ifS(j)⋅xj≤fS(Vi), ∀ i∈ V, _j=1^if_S(j)· x_j≤ f_S(V_i), ∑i∈Vc(i)⋅xi≤b. _i∈ Vc(i)· x_i≤ b. We prove in Appendix D that the optimum of Equation 9 is equal to Λ2(S) ^2(S). Though we have assumed S=1,2,…,pS=\1,2,…,p\ and V∖S=p+1,p+2,…,nV S=\p+1,p+2,…,n\, Equation 9 actually does not require the elements of S to be arranged before the elements of V∖SV S in the ground set. The indexes of their elements can be arbitrarily interleaved. This is because in the first constraint of Equation 9, fS(j)=0f_S(j)=0 for any element j∈Sj∈ S and thus it would not increase the value of the left-hand side. On the right-hand side, fS(Vi)f_S(V_i) never decreases as i increases. Thus, if the first constraint holds for all i∈V∖Si∈ V S, it would also hold for all i∈Si∈ S. This observation will be useful when later we introduce a unified upper bound based on multiple base sets S, where it is difficult to separate the indexes of S and V∖SV S for all base sets. 3.3 Combining removing and slicing strategies We can combine the removing strategy and slicing strategy, bringing forth a tighter upper bound Λ3 ^3. Given a set S, we denote the upper bound Λ2(S) ^2(S) generated with a budget x∈[0,b]x∈[0,b] as Φ(x) (x). The new upper bound Λ3 ^3 is defined as follows: Λ3(S)=maxx∈[0,c(S)](Φ(b−c(S)+x)−G−(x)), ^3(S)= _x∈[0,c(S)]( (b-c(S)+x)-G_-(x)), where G−(x)G_-(x) is defined in Equation 5. According to the property of Λ2(S) ^2(S), Φ(x) (x) is a non-decreasing function and Φ(x)≥maxT⊆V∖S,c(T)≤xfS(T) (x)≥ _T V S,\,c(T)≤ xf_S(T). Letting x=maxc(OPT∪S)−b,0x= \c(OPT∪ S)-b,0\, similar to the derivation in Λ1(S) ^1(S), we have Φ(b−c(S)+x)−G−(x) (b-c(S)+x)-G_-(x) ≥Φ(c(OPT∪S)−c(S))−G−(c(OPT∪S)−c(OPT)) ≥ (c(OPT∪ S)-c(S))-G_-(c(OPT∪ S)-c(OPT)) =Φ(c(OPT∖S))−G−(c(S∖OPT)) = (c(OPT S))-G_-(c(S OPT)) ≥fS(OPT∖S)−fOPT(S∖OPT) ≥ f_S(OPT S)-f_OPT(S OPT) =f(OPT)−f(S), =f(OPT)-f(S), which implies that f(S)+Λ3(S)≥f(OPT)f(S)+ ^3(S)≥ f(OPT). In addition, we have Λ2(S) ^2(S) =Φ(b)≥maxx∈[0,c(S)]Φ(b−c(S)+x) = (b)≥ _x∈[0,c(S)] (b-c(S)+x) ≥maxx∈[0,c(S)](Φ(b−c(S)+x)−G−(x))=Λ3(S), ≥ _x∈[0,c(S)]( (b-c(S)+x)-G_-(x))= ^3(S), which shows that Λ3 ^3 is at least as good as Λ2 ^2. The calculation of Λ3 ^3 can also be written as a linear program by adding the removing item to Equation 9. By similar arguments to the computational complexity of Λ1(S) ^1(S) in Section 3.1.1, the time complexity to compute Λ3(S) ^3(S) is also O(nlogn)=O(|V|log|V|)O(n n)=O(|V| |V|), the same as Λ0(S) ^0(S), Λ1(S) ^1(S) and Λ2(S) ^2(S). Please refer to Appendix E for details. 3.4 Enhancing bounds with multiple base sets If we calculate an upper bound with one base set S only (e.g., an empty set or the output solution of an algorithm), the result may not be satisfying. To tighten the bound, we can compute multiple upper bounds with different base sets (such as all the intermediate sets generated by a greedy algorithm for the MSMK problem) and choose the lowest upper bound obtained as the final result. This enhancement can be conducted on all the proposed new upper bounds (Λ1 ^1 to Λ3 ^3). We denote the final result for such an enumeration based on Λi ^i as Λi+ ^i+, i.e., Λi+=minS∈S1,S2,…f(S)+Λi(S) ^i+= _S∈\S_1,S_2,…\f(S)+ ^i(S). In the above approach, one upper bound is computed for each base set separately. Alternatively, we can compute a shared upper bound for multiple base sets, producing an even tighter bound. 3.4.1 Unified augmentation for Λ0 ^0 and Λ1 ^1 We first construct a linear program as follows: max z z (10) subject to ∀S⊆V,z≤f(S)+Λ(S,), ∀ S V, z≤ f(S)+ (S,x), ∑i∈Vc(i)⋅xi≤b, _i∈ Vc(i)· x_i≤ b, where =⟨x1,x2,…,xn⟩∈[0,1]nx= x_1,x_2,…,x_n ∈[0,1]^n is an indicator vector. Let x^OPT be the indicator vector of the optimal solution OPTOPT to the MSMK problem (where xiOPT=1x^OPT_i=1 if i∈OPTi∈ OPT, and xiOPT=0x^OPT_i=0 otherwise). If function Λ(S,) (S,x) satisfies f(S)+Λ(S,)≥f(OPT)f(S)+ (S,x^OPT)≥ f(OPT) for every set S⊆VS V, it is easy to see that the optimal value of Equation 10 must be no less than f(OPT)f(OPT). Equation 10 cannot be solved efficiently because there is an exponential number of possible sets S (or constraints). However, we can relax Equation 10 by considering the constraints relevant to a collection of base sets S1,S2,…,Sm\S_1,S_2,…,S_m\ only. max z z (11) subject to ∀i∈1,2,…,m,z≤f(Si)+Λ(Si,), ∀ i∈\1,2,…,m\, z≤ f(S_i)+ (S_i,x), ∑i∈Vc(i)⋅xi≤b. _i∈ Vc(i)· x_i≤ b. The optimal value of this linear program is not less than that of Equation 10, and thus guaranteed to be an upper bound on f(OPT)f(OPT). We call this procedure the “unified” augmentation method, since it forces each base set SiS_i to share the same indicator vector x. For Λ0 ^0 and Λ1 ^1, we can design Λ(S,) (S,x) according to the objective functions in their linear program representations (Equation 7 and Equation 6). Specifically, we define Λ0(S,) ^0(S,x) and Λ1(S,) ^1(S,x) as follows: Λ0(S,)=∑i∈V∖SfS(i)⋅xi, ^0(S,x)= _i∈ V Sf_S(i)· x_i, (12) Λ1(S,)=∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi). ^1(S,x)= _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i). (13) Apparently, Λ0(S,)≥Λ1(S,) ^0(S,x)≥ ^1(S,x). For any set S⊆VS V, we have f(S)+Λ1(S,) f(S)+ ^1(S,x^OPT) (14) = = f(S)+∑i∈V∖SfS(i)⋅xiOPT−∑i∈SfV∖i(i)⋅(1−xiOPT) f(S)+ _i∈ V Sf_S(i)· x^OPT_i- _i∈ Sf_V \i\(i)·(1-x^OPT_i) = = f(S)+∑i∈OPT∖SfS(i)−∑i∈S∖OPTfV∖i(i) f(S)+ _i∈ OPT Sf_S(i)- _i∈ S OPTf_V \i\(i) ≥ ≥ f(S)+fS(OPT)−fOPT(S)=f(OPT). f(S)+f_S(OPT)-f_OPT(S)=f(OPT). Thus, we can instantiate Λ(S,) (S,x) with Λ0(S,) ^0(S,x) or Λ1(S,) ^1(S,x) in Equation 11, and solve Equation 11 to obtain an upper bound on f(OPT)f(OPT). We denote the resulting bounds as Λ0∗ ^0* and Λ1∗ ^1*. 3.4.2 Unified augmentation for Λ2 ^2 and Λ3 ^3 To calculate a unified upper bound with multiple base sets S1,S2,…,SmS_1,S_2,…,S_m for Λ2 ^2, we construct the following linear program, where the second and third constraints correspond to conditions (i) and (iv) of Definition 1, and Vj:=1,2,…,jV_j:=\1,2,…,j\: max z z (15) subject to ∀i∈1,2,…,m,z≤f(Si)+∑j∈Vvji, ∀ i∈\1,2,…,m\, z≤ f(S_i)+ _j∈ Vv^i_j, ∀i∈1,2,…,m and j∈V,vji≤fSi(j)⋅xj, ∀ i∈\1,2,…,m\ and j∈ V, v^i_j≤ f_S_i(j)· x_j, ∀i∈1,2,…,m and j∈V,∑k=1jvki≤fSi(Vj), ∀ i∈\1,2,…,m\ and j∈ V, _k=1^jv^i_k≤ f_S_i(V_j), ∑i∈Vc(i)⋅xi≤b. _i∈ Vc(i)· x_i≤ b. Equation 15 can be viewed as an extension of Equation 9 to multiple base sets (recall that Equation 9 allows the indexes of the elements in S and V∖SV S to be interleaved arbitrarily). It is easy to prove that the optimum of Equation 15 dominates f(OPT)f(OPT), since setting ⟨x1,x2,…,xn⟩= x_1,x_2,…,x_n =x^OPT (the indicator vector of OPTOPT) and z=f(OPT)z=f(OPT) can satisfy all the constraints therein. To calculate a unified upper bound for Λ3 ^3, we can further add the removing item to the first constraint of Equation 15 as follows: max z z (16) subject to ∀i∈1,2,…,m,z≤f(Si)+∑j∈Vvji−∑j∈SifV∖j(j)⋅(1−xj), ∀ i∈\1,2,…,m\, z≤ f(S_i)+ _j∈ Vv^i_j- _j∈ S_if_V \j\(j)·(1-x_j), ∀i∈1,2,…,m and j∈V,vji≤fSi(j)⋅xj, ∀ i∈\1,2,…,m\ and j∈ V, v^i_j≤ f_S_i(j)· x_j, ∀i∈1,2,…,m and j∈V,∑k=1jvki≤fSi(Vj), ∀ i∈\1,2,…,m\ and j∈ V, _k=1^jv^i_k≤ f_S_i(V_j), ∑i∈Vc(i)⋅xi≤b. _i∈ Vc(i)· x_i≤ b. Equation 16 can be viewed as an extension of Equation 17 to multiple base sets. Similarly, the optimum of Equation 16 dominates f(OPT)f(OPT), since setting ⟨x1,x2,…,xn⟩= x_1,x_2,…,x_n =x^OPT and z=f(OPT)z=f(OPT) can satisfy all the constraints therein. We denote the upper bounds obtained from Equations (15) and (16) as Λ2∗ ^2* and Λ3∗ ^3* respectively. 4 Experiments We carry out experiments on three different applications to demonstrate the advantage of our proposed bounds (Λ1 ^1, Λ2 ^2, Λ3 ^3 and their augmentations) over the previous bounds Λ0 ^0 and Λ0+ ^0+ in [25]. The experiments are conducted on a Windows machine with a 3.8GHz Intel Xeon W-2235 CPU and 32GB RAM with code written in Python. Feature selection. Feature selection is a procedure widely used in machine learning [1, 4, 8]. Given a feature set V which contains all features that a data point in a training set may have, the goal is to select a subset S⊆VS V, with the highest utility subject to a limited budget, to construct a classification model. We adopt the following entropy function [3] to determine the utility value of a feature set S⊆VS V: f(S)=−∑x∈XS∑y∈Yp(x,y)logp(x,y),f(S)=- _x∈ X_S _y∈ Yp(x,y) p(x,y), where XSX_S is the feature matrix indexed by S, Y is the set of labels, and p(x,y)p(x,y) is the joint distribution on (XS,Y)(X_S,Y). We experiment with Adult Income, a real-world dataset from [5]. This dataset contains 32561 individuals with a variety of features. We retrieve 111 binary features from the dataset as in [13] and then randomly generate 20 ground sets each containing 100 features by uniformly sampling from these 111 binary features. Maximum coverage. Maximum coverage is a classical optimization problem with numerous practical applications, such as influence maximization [26, 14] and sensor placement [16, 18]. It addresses the challenge of using limited resources to achieve the highest utility. Given a graph G=(V,E)G=(V,E) where each vertex v∈Vv∈ V has an associated cost c(v)c(v), the objective is to find a vertex subset S⊆VS V with limited total cost that maximizes a coverage function: f(S)=|NG(S)|,f(S)=|N_G(S)|, where NG(S)N_G(S) is the graph neighborhood function that returns a set containing all vertices in S and all vertices adjacent to any vertex in S in the graph G. We experiment with ego-facebook and com-youtube, two real-world datasets from [19]. ego-facebook contains 4039 nodes and 88234 edges; com-youtube (top 5000 communities) contains 39841 nodes and 224234 edges. For each dataset, we randomly construct 20 ground sets each containing 1000 nodes by uniformly sampling from the dataset. Revenue maximization. In social advertising, we would like to choose seed users who will advertise products to their neighbors on social networks. A social network is modeled by a graph G=(V,E)G=(V,E), where each node v∈Vv∈ V represents a user, and each edge (u,v)∈E(u,v)∈ E has a weight wuvw_uv describing the influence of u on v. Each user v will be paid a cost c(v)c(v) for advertising products if chosen as a seed user. The goal is to select a subset S⊆VS V of seed users within a budget to maximize product revenue. We adopt the expected product revenue function defined in [6]: f(S)=∑v∈V(∑u∈Swuv)0.9,f(S)= _v∈ V ( _u∈ Sw_uv )^0.9, where the exponent 0.90.9 measures diminishing returns. We experiment with a real-world dataset Caltech36 from [23] containing 769 users. We randomly generate 20 ground sets each containing 100 nodes by uniformly sampling from the dataset. Cost and budget setting. All the datasets lack a cost function. When conducting the experiments for each ground set, we randomly assign a cost to each element in three different ways: (a) all element costs are generated from U(1,5)U(1,5), where U(x,y)U(x,y) represents a uniform distribution between x and y; (b) 80% element costs are generated from U(1,5)U(1,5) and 20% element costs are generated from U(5,20)U(5,20) (most costs are small while some are large); (c) 80% element costs are generated from U(1,5)U(1,5) and 20% element costs are generated from U(0,1)U(0,1) (most costs are large while some are small). Similar performance trends are observed for these three distributions. We present the results for (a) here and defer the results for (b) and (c) to Appendix F. For cost setting (a), we conduct experiments for all ground sets generated with different budgets from 6 to 40 (step size 1). Algorithms and intermediate sets. For each problem instance, we run the modified greedy algorithm MGreedy [27] and the Greedy+Max algorithm [28]. The experimental results for the two algorithms show similar trends. Due to space limitations, we focus on presenting the results of MGreedy in this paper. MGreedy starts with an empty solution set and employs a greedy heuristic. In each iteration, the greedy heuristic finds the element with the highest marginal density among all elements that can fit into the remaining budget, and adds it to the solution set. The procedure repeats until no more element can be added to the solution set S due to budget violation. MGreedy then finds an element v∗v^* which maximizes f(v∗)f(\v^*\) and compares it with f(S)f(S) and outputs the one with a larger function value. The approximation factor of MGreedy is between 0.427 and 0.42945 [11, 17]. We calculate the upper bounds Λ0 ^0, Λ1 ^1, Λ2 ^2, Λ3 ^3 using the empty set ∅ or the algorithm’s output solution S as the base set, and their enumerated and unified augmentations Λi+ ^i+ and Λi∗ ^i* based on all intermediate sets generated by the algorithm (i.e., those produced by the greedy heuristic as well as the singleton set v∗\v^*\). Λi ^i and Λi+ ^i+ are calculated by the formulas presented. Λi∗ ^i* is calculated by solving the linear program presented, for which we use the SciPy library in Python. Then, we divide the MGreedy solution by the upper bound to derive its approximation guarantee. For each dataset, there are 700 problem instances (20 ground sets × 35 different budgets from 6 to 40). We present the box plot to illustrate the experimental results across all instances. We use a common box plot showing the first quartile (25th percentile) and the third quartile (75th percentile) as a box, and the boundaries of the whiskers based on 1.5 times the interquartile range (the distance between the third and first quartiles). In addition, the green triangle presents the mean value. (a) Adult Income (b) Caltech36 (c) ego-facebook (d) com-youtube Figure 3: Actual approximation guarantee plots for different upper bounds Figure 3 presents the approximation guarantees derived from different upper bounds for the MGreedy algorithm. We can make the following observations from the results. First, data-dependent upper bounds typically certify much higher approximation guarantees than the worst-case theoretical result (recall that MGreedy’s approximation factor is between 0.427 and 0.42945). The unified upper bounds Λi∗ ^i* confirm that MGreedy solutions are quite close to optimal (within 10% in most cases). Second, Λ2/Λ2+/Λ2∗ ^2/ ^2+/ ^2* are significantly tighter than Λ0/Λ0+/Λ0∗ ^0/ ^0+/ ^0* for most problem instances, which demonstrates the advantage of the slicing strategy. Λ3/Λ3+/Λ3∗ ^3/ ^3+/ ^3* (resp. Λ1/Λ1+/Λ1∗ ^1/ ^1+/ ^1*) are at least as good as Λ2/Λ2+/Λ2∗ ^2/ ^2+/ ^2* (resp. Λ0/Λ0+/Λ0∗ ^0/ ^0+/ ^0*) as proved. As seen from Figure 3(b), the augmentations Λ3+/Λ3∗ ^3+/ ^3* (resp. Λ1+/Λ1∗ ^1+/ ^1*) are much tighter than Λ2+/Λ2∗ ^2+/ ^2* (resp. Λ0+/Λ0∗ ^0+/ ^0*) for the Caltech36 dataset, which will be further analyzed below. Third, upper bounds calculated with only one base set ∅ or S can be rather loose (e.g., Λ0(∅) ^0( ) and Λ1(∅) ^1( ) for the Adult Income dataset). The relative performance of Λi(∅) ^i( ) and Λi(S) ^i(S) varies with the dataset. Upper bounds calculated with multiple base sets are normally considerably tighter. The unified upper bounds Λi∗ ^i* are remarkably tighter than the enumerated upper bounds Λi+ ^i+ in many cases. We present two reasons accounting for the superior performance of the removing strategy on the Caltech36 dataset. First, an element e in the Caltech36 dataset is more likely to have a higher cutoff density dV∖e(e)d_V \e\(e) compared with the other three datasets, which makes the removing strategy more effective. In Figure 4, we present the dV∖e(e)d_V \e\(e) values of elements from different ground sets. The plot contains data from 20000/20000/2000/2000 elements from the 20 ground sets of the ego-facebook/com-youtube/Caltech36/Adult Income datasets, respectively. Figure 4: Cutoff densities of elements in four datasets Second, recall that the enumerated augmentation Λi+ ^i+ is the lowest upper bound among all those obtained from taking the intermediate sets of MGreedy as base sets. If Λ1+ ^1+ or Λ3+ ^3+ is given by the upper bound obtained from an empty set (the initial greedy solution), the removing strategy does not further tighten the bound because Λ1(∅) ^1( ) =maxx∈[0,c(∅)]G+(b−c(∅)+x)−G−(x) = _x∈[0,c( )] \G_+(b-c( )+x)-G_-(x) \ =G+(b−c(∅)+0)−G−(0) =G_+(b-c( )+0)-G_-(0) =G+(b) =G_+(b) =Λ0(∅), = ^0( ), and a similar argument also holds for Λ3+ ^3+. Λ3+ ^3+ is never equal to Λ3(∅) ^3( ) for the Caltech36 dataset, while it is common for the other three datasets as illustrated in Table 1. This observation explains the reason why the com-youtube dataset fails to have a better Λ3+ ^3+ than Λ2+ ^2+ despite its cutoff densities dV∖e(e)d_V \e\(e) not being close to 0. For similar reasons, the unified augmentations Λ1∗/Λ3∗ ^1*/ ^3* have the same performance tendencies as the enumerated augmentations Λ1+/Λ3+ ^1+/ ^3+. Table 1: Problem instances where Λ3+=Λ3(∅) ^3+= ^3( ) Dataset # of Λ3+=Λ3(∅) ^3+= ^3( ) Total # Percentage Adult Income 658 700 94.0% Caltech36 0 700 0.0% ego-facebook 396 700 56.8% com-youtube 700 700 100% To evaluate the computational efficiency of our upper bounds, we present the box plots of computational time in Figure 5. The computational times of Λ2/Λ2+ ^2/ ^2+ and Λ0/Λ0+ ^0/ ^0+ are nearly the same for all the datasets except Adult Income.222Detailed examinations show that the number of elements visited in V∖SV S for computing Λ2/Λ2+ ^2/ ^2+ is much larger than that for computing Λ0/Λ0+ ^0/ ^0+ for the Adult Income dataset, while these numbers are similar for other datasets. This demonstrates the computational efficiency of the slicing strategy. The computational times of Λ1/Λ1+ ^1/ ^1+ and Λ0/Λ0+ ^0/ ^0+ are also generally close for all the datasets. This shows that the removing strategy does not introduce much additional computational overhead. Comparing enumerated and unified augmentations, the computational times of Λ0∗/Λ1∗ ^0*/ ^1* are similar to Λ0+/Λ1+ ^0+/ ^1+, whereas the computational times of Λ2∗/Λ3∗ ^2*/ ^3* can be much higher than Λ2+/Λ3+ ^2+/ ^3+. This is because the number of constraints is independent of the ground set size in the linear program of unified augmentations Λ0∗/Λ1∗ ^0*/ ^1*, while it is proportional to the ground set size in the linear program of unified augmentations Λ2∗/Λ3∗ ^2*/ ^3*. (a) Adult Income (b) Caltech36 (c) ego-facebook (d) com-youtube Figure 5: Computational time plots for different upper bounds For large-scale problems where computational time may be a concern, we recommend using the enumerated augmentation Λ3+ ^3+ and the unified augmentation Λ1∗ ^1*. They often have much lower computational times than the unified augmentations Λ2∗ ^2* and Λ3∗ ^3* (see ego-facebook and com-youtube results in Figure 5, where the ground set size is 1000), while the better bound between Λ3+ ^3+ and Λ1∗ ^1* is generally close to Λ2∗ ^2* and Λ3∗ ^3* as shown in Figure 3. 5 Conclusion In this paper, we have proposed a removing strategy and a slicing strategy for constructing new data-dependent upper bounds for submodular maximization with a knapsack constraint. The upper bounds constructed are shown to be much tighter than existing bounds by extensive experiments. In future work, we would like to find the ways to extend our techniques to submodular maximization problems with other constraints, such as matroid and p-system. Acknowledgments This research is supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (Award MOE-T2EP20122-0007). Jing Tang’s work is also partially supported by National Key R&D Program of China under Grant No. 2024YFA1012700, by the National Natural Science Foundation of China (NSFC) under Grant No. 62402410, and by Guangdong Provincial Project (No. 2023QN10X025). References [1] Magda Amiridi, Nikos Kargas, and Nicholas D Sidiropoulos. Information-theoretic feature selection via tensor decomposition and submodularity. IEEE Transactions on Signal Processing, 69:6195–6205, 2021. [2] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1497–1514. SIAM, 2014. [3] Eric Balkanski, Sharon Qian, and Yaron Singer. Instance specific approximations for submodular maximization. In International Conference on Machine Learning, pages 609–618. PMLR, 2021. [4] Wei-Xuan Bao, Jun-Yi Hang, and Min-Ling Zhang. Submodular feature selection for partial label learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 26–34, 2022. [5] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: https://doi.org/10.24432/C5XW20. [6] Adam Breuer, Eric Balkanski, and Yaron Singer. The fast algorithm for submodular maximization. In International Conference on Machine Learning, pages 1134–1143. PMLR, 2020. [7] Deeparnab Chakrabarty and Luc Cote. A primal-dual analysis of monotone submodular maximization. arXiv preprint arXiv:2311.07808, 2023. [8] Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.3975, 2011. [9] Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. Revenue submodularity. In Proceedings of the 10th ACM Conference on Electronic Commerce, pages 243–252, 2009. [10] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, 1998. [11] Moran Feldman, Zeev Nutov, and Elad Shoham. Practical budgeted submodular maximization. Algorithmica, 85:1332–1371, 2023. [12] Ryan Gomes and Andreas Krause. Budgeted nonparametric learning from data streams. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 391–398, 2010. [13] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. In International conference on machine learning, pages 2544–2553. PMLR, 2018. [14] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003. [15] Samir Khuller, Anna Moss, and Joseph (Seffi) Naor. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39–45, 1999. URL: https://w.sciencedirect.com/science/article/pii/S0020019099000319, doi:10.1016/S0020-0190(99)00031-9. [16] Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008. [17] Ariel Kulik, Roy Schwartz, and Hadas Shachnai. A refined analysis of submodular greedy. Operations Research Letters, 49(4):507–514, 2021. [18] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 420–429, 2007. [19] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014. [20] Hui Lin and Jeff Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 912–920, 2010. [21] Erik Lindgren, Shanshan Wu, and Alexandros G Dimakis. Leveraging sparsity for efficient submodular data summarization. Advances in Neural Information Processing Systems, 29, 2016. [22] George L. Nemhauser and Laurence A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177–188, 1978. [23] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 4292–4293, 2015. URL: https://networkrepository.com. [24] Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43, 2004. [25] Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, and Junsong Yuan. Revisiting modified greedy algorithm for monotone submodular maximization with a knapsack constraint. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1–22, 2021. [26] Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. Online processing algorithms for influence maximization. In Proceedings of the 2018 ACM SIGMOD International Conference on Management of Data, pages 991–1005. ACM, 2018. [27] Laurence A. Wolsey. Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Mathematics of Operations Research, 7(3):410–425, 1982. [28] Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. “bring your own greedy”+max: near-optimal 1/2-approximations for submodular knapsack. In International Conference on Artificial Intelligence and Statistics, pages 3263–3274. PMLR, 2020. [29] Ping Zhang, Zhifeng Bao, Yuchen Li, Guoliang Li, Yipeng Zhang, and Zhiyong Peng. Trajectory-driven influential billboard placement. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’18, page 2748–2757, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3219819.3219946. Appendix A Equivalence between the optimum of Equation (6) and Λ1(S) ^1(S) Lemma 4. For each value t∈[0,c(S)]t∈[0,c(S)], there exists an indicator vector =⟨x1,x2,…,xn⟩∈[0,1]nx= x_1,x_2,…,x_n ∈[0,1]^n that satisfies G+(b−c(S)+t)−G−(t)=∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi)G_+(b-c(S)+t)-G_-(t)= _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i) and ∑i∈Vc(i)⋅xi≤b _i∈ Vc(i)· x_i≤ b. Proof. We prove this lemma by constructing an x that satisfies the constraints. Let r be the index of the last element covered by G+(b−c(S)+t)G_+(b-c(S)+t), i.e., ∑i=p+1r−1fS(i)<G+(b−c(S)+t)≤∑i=p+1rfS(i) _i=p+1^r-1f_S(i)<G_+(b-c(S)+t)≤ _i=p+1^rf_S(i). Similarly, let s be the index of the last element covered by G−(t)G_-(t), i.e., ∑i=1s−1fV∖i(i)<G−(t)≤∑i=1sfV∖i(i) _i=1^s-1f_V \i\(i)<G_-(t)≤ _i=1^sf_V \i\(i). We construct an x as follows: xi=0,1≤i≤s−1,∑i=1sc(i)−tc(s),i=s,1,s+1≤i≤p,1,p+1≤i≤r−1,b−c(S)+t−∑i=p+1r−1c(i)c(r),i=r,0,r+1≤i≤n.x_i= \ aligned 0&,&1≤ i≤ s-1,\\ _i=1^sc(i)-tc(s)&,&i=s,\\ 1&,&s+1≤ i≤ p,\\ 1&,&p+1≤ i≤ r-1,\\ b-c(S)+t- _i=p+1^r-1c(i)c(r)&,&i=r,\\ 0&,&r+1≤ i≤ n. aligned . Then, we have G+(b−c(S)+t) G_+(b-c(S)+t) = = ∑i=1r−1fS(i)+(b−c(S)+t−∑i=1r−1c(i))⋅fS(r)c(r) _i=1^r-1f_S(i)+ (b-c(S)+t- _i=1^r-1c(i) )· f_S(r)c(r) = = ∑i=p+1r−1fS(i)⋅xi+fS(r)⋅xr=∑i∈V∖SfS(i)⋅xi, _i=p+1^r-1f_S(i)· x_i+f_S(r)· x_r= _i∈ V Sf_S(i)· x_i, and G−(t)=∑i=1s−1fV∖i(i)+(t−∑i=1s−1c(i))⋅fV∖s(s)c(s) G_-(t)= _i=1^s-1f_V \i\(i)+ (t- _i=1^s-1c(i) )· f_V \s\(s)c(s) =∑i=1s−1fV∖i(i)⋅(1−xi)+fV∖s(s)⋅(1−xs)=∑i∈SfV∖i(i)⋅(1−xi). = _i=1^s-1f_V \i\(i)·(1-x_i)+f_V \s\(s)·(1-x_s)= _i∈ Sf_V \i\(i)·(1-x_i). Thus, G+(b−c(S)+t)−G−(t)=∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi)G_+(b-c(S)+t)-G_-(t)= _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i). Finally, ∑i∈Vc(i)⋅xi=∑i∈Sc(i)⋅xi+∑i∈V∖Sc(i)⋅xi=c(S)−t+b−c(S)+t=b. _i∈ Vc(i)· x_i= _i∈ Sc(i)· x_i+ _i∈ V Sc(i)· x_i=c(S)-t+b-c(S)+t=b. Hence, the x constructed satisfies the two constraints. ∎ Lemma 5. For each indicator vector =⟨x1,x2,…,xn⟩∈[0,1]nx= x_1,x_2,…,x_n ∈[0,1]^n that satisfies ∑i∈Vc(i)⋅xi≤b _i∈ Vc(i)· x_i≤ b, there exists a value t∈[0,c(S)]t∈[0,c(S)] such that G+(b−c(S)+t)−G−(t)≥∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi)G_+(b-c(S)+t)-G_-(t)≥ _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i). Proof. It suffices to prove the claim for an indicator vector producing the optimal function value of Equation (6), which maximizes the right-hand side of the inequality to be proved. Since the coefficients of all variables xix_i’s are non-negative, the objective function value of Equation (6) never decreases with increasing xix_i values. Thus, without loss of generality, we can assume that the indicator vector producing the optimal function value of Equation (6) satisfies ∑i∈Vc(i)⋅xi=b _i∈ Vc(i)· x_i=b. Let t=∑i∈V∖Sc(i)⋅xi−b+c(S)=c(S)−∑i∈Sc(i)⋅xi≥0t= _i∈ V Sc(i)· x_i-b+c(S)=c(S)- _i∈ Sc(i)· x_i≥ 0. We can infer that ∑i∈V∖SfS(i)⋅xi≤G+(∑i∈V∖Sc(i)⋅xi) _i∈ V Sf_S(i)· x_i≤ G_+( _i∈ V Sc(i)· x_i) since G+G_+ greedily picks elements with the highest marginal densities. Thus, ∑i∈V∖SfS(i)⋅xi≤G+(b−c(S)+t). _i∈ V Sf_S(i)· x_i≤ G_+(b-c(S)+t). Similarly, we can infer that ∑i∈SfV∖i(i)⋅(1−xi)≥G−(∑i∈Sc(i)⋅(1−xi)) _i∈ Sf_V \i\(i)·(1-x_i)≥ G_-( _i∈ Sc(i)·(1-x_i)) since G−G_- greedily picks elements with the lowest cutoff densities. Moreover, it follows from ∑i∈Vc(i)⋅xi=b _i∈ Vc(i)· x_i=b that ∑i∈Sc(i)⋅(1−xi)=c(S)−∑i∈Sc(i)⋅xi=c(S)−b+∑i∈V∖Sc(i)⋅xi _i∈ Sc(i)·(1-x_i)=c(S)- _i∈ Sc(i)· x_i=c(S)-b+ _i∈ V Sc(i)· x_i. Therefore, ∑i∈SfV∖i(i)⋅(1−xi) _i∈ Sf_V \i\(i)·(1-x_i) ≥G−(∑i∈Sc(i)⋅(1−xi)) ≥ G_-( _i∈ Sc(i)·(1-x_i)) =G−(c(S)−b+∑i∈V∖Sc(i)⋅xi)=G−(t). =G_-(c(S)-b+ _i∈ V Sc(i)· x_i)=G_-(t). Hence, we can conclude that G+(b−c(S)+t)−G−(t)≥∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi)G_+(b-c(S)+t)-G_-(t)≥ _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i). ∎ Lemma 4 and Lemma 5 together guarantee the equivalence between the optimum of Equation 6 and Λ1(S) ^1(S). Appendix B Proof of Lemma 2 Lemma 2. For any set T⊆V∖ST V S with c(T)≤bc(T)≤ b, fS(T)f_S(T) has a valid partition with respect to S. Proof. We construct a valid partition of fS(T)f_S(T) to prove this lemma. Assume that T has m elements: T=t1,t2,…,tmT=\t_1,t_2,…,t_m\ where p+1≤t1<t2<⋯<tm≤np+1≤ t_1<t_2<·s<t_m≤ n. To simplify presentation, we define Ti:=t1,t2,…,tiT_i:=\t_1,t_2,…,t_i\ and T0:=∅T_0:= . For each element ti∈Tt_i∈ T, we set sti=dS∪Ti−1(ti)dS(ti)⋅c(ti)s_t_i= d_S∪ T_i-1(t_i)d_S(t_i)· c(t_i) and vti=fS∪Ti−1(ti)v_t_i=f_S∪ T_i-1(t_i). For each element j∈V∖Tj∈ V T, we set sj=0s_j=0 and vj=0v_j=0. We verify all the conditions of Definition 1. For condition (i), ∑i=1nvi=∑i=1mvti=∑i=1mfS∪Ti−1(ti)=fS(T). _i=1^nv_i= _i=1^mv_t_i= _i=1^mf_S∪ T_i-1(t_i)=f_S(T). For condition (i), ∑i=1nsi _i=1^ns_i =∑i=1msti=∑i=1mdS∪Ti−1(ti)dS(ti)⋅c(ti)≤∑i=1mc(ti)=c(T)≤b, = _i=1^ms_t_i= _i=1^m d_S∪ T_i-1(t_i)d_S(t_i)· c(t_i)≤ _i=1^mc(t_i)=c(T)≤ b, where the first inequality is due to the submodularity of f. For condition (i), for each element ti∈Tt_i∈ T, dS(ti)⋅sti=dS∪Ti−1(ti)⋅c(ti)=fS∪Ti−1(ti)=vti,d_S(t_i)· s_t_i=d_S∪ T_i-1(t_i)· c(t_i)=f_S∪ T_i-1(t_i)=v_t_i, and for each element j∈V∖Tj∈ V T, dS(j)⋅sj=0=vj.d_S(j)· s_j=0=v_j. For condition (iv), for each element j∈V∖Tj∈ V T, let r be the highest index satisfying tr≤jt_r≤ j (define r=0r=0 and tr=0t_r=0 if j<t1j<t_1), then fS(Vj)≥∑k=1rfS∪Tk−1(tk)=∑k=1rvtk=∑k=1trvk=∑k=1jvk,f_S(V_j)≥ _k=1^rf_S∪ T_k-1(t_k)= _k=1^rv_t_k= _k=1^t_rv_k= _k=1^jv_k, where the inequality is due to the monotonicity of f. ∎ Appendix C Proof of Lemma 3 Lemma 3. The maximum value v that has a valid partition is given by Λ2(S) ^2(S). Proof. Let the cost sequence generated for computing Λ2(S) ^2(S) be s1,s2,…,sns_1,s_2,…,s_n and the corresponding value sequence be v1,v2,…,vnv_1,v_2,…,v_n. If s1,s2,…,sns_1,s_2,…,s_n do not use up the budget b, i.e., ∑i=p+1ndS∪Vi−1(i)dS(i)⋅c(i)<b _i=p+1^n d_S∪ V_i-1(i)d_S(i)· c(i)<b, the claim is straightforward since ∑i=1nvi=∑i=1nfS∪Vi−1(i)=fS(Vn) _i=1^nv_i= _i=1^nf_S∪ V_i-1(i)=f_S(V_n) must be the maximum possible due to condition (iv) of Definition 1 (by setting i=ni=n). Now assume that ∑i=1nsi=b _i=1^ns_i=b. Let t be the lowest index satisfying ∑i=1tsi=b _i=1^ts_i=b. By the procedure for computing Λ2(S) ^2(S), • for each p+1≤i<tp+1≤ i<t, si=dS∪Vi−1(i)dS(i)⋅c(i)s_i= d_S∪ V_i-1(i)d_S(i)· c(i) and ∑j=1ivj=fS(Vi) _j=1^iv_j=f_S(V_i); • st=(b−∑j=p+1t−1dS∪Vj−1(j)dS(j)⋅c(j))⋅dS(t)s_t= (b- _j=p+1^t-1 d_S∪ V_j-1(j)d_S(j)· c(j) )· d_S(t) and ∑j=1tvj=Λ2(S) _j=1^tv_j= ^2(S); • for each i>ti>t, si=0s_i=0 and ∑j=1ivj=Λ2(S) _j=1^iv_j= ^2(S). We prove the lemma by contradiction. Let v~ v be the maximum value that has a valid partition. Assume that v~>Λ2(S) v> ^2(S). There can be multiple valid partitions of v~ v. Among all valid partitions of v~ v, we pick one with the lowest total cost. If there are multiple valid partitions with the same lowest total cost, we pick one whose cost sequence is the last in the lexicographic order (for any two cost sequences, we can check the lowest index where the costs differ; the sequence with a smaller cost at this index is placed before the other sequence according to the lexicographic order; the lexicographic order is a total order). Let s~1,s~2,…,s~n s_1, s_2,…, s_n be the cost sequence and v~1,v~2,…,v~n v_1, v_2,…, v_n be the value sequence in this valid partition, where ∑i=1nv~i=v~ _i=1^n v_i= v. Now we check the difference between the two sequences. We iterate through the sequence ⟨p+1,p+2,…,n⟩ p+1,p+2,…,n to find the first element q where sq≠s~qs_q≠ s_q. We can assume q≤tq≤ t, since otherwise ∑i=1ts~i=∑i=1tsi=b _i=1^t s_i= _i=1^ts_i=b and hence s~q=0=sq s_q=0=s_q must hold. If s~q>sq s_q>s_q, we must have q<tq<t, because s~t≤b−∑i=1t−1s~i=∑i=1tsi−∑i=1t−1s~i=st s_t≤ b- _i=1^t-1 s_i= _i=1^ts_i- _i=1^t-1 s_i=s_t. We can construct a new cost sequence s1,…,sq−1,sq,s~q+1,…,s~ns_1,…,s_q-1,s_q, s_q+1,…, s_n and a new value sequence v1,…,vq−1,v_1,…,v_q-1, ∑i=1qv~i−∑i=1q−1vi,v~q+1,…,v~n _i=1^q v_i- _i=1^q-1v_i, v_q+1,…, v_n. We verify that they satisfy all the conditions of Definition 1. Condition (i) holds because the total value remains unchanged. Condition (i) holds because the total cost ∑i=1qsi+∑i=q+1ns~i<∑i=1qs~i+∑i=q+1ns~i≤b _i=1^qs_i+ _i=q+1^n s_i< _i=1^q s_i+ _i=q+1^n s_i≤ b. Condition (i) obviously holds for any i≠qi≠ q as the cost-value pair of index i is inherited from an existing valid partition. For i=qi=q, we have dS(q)⋅sq≥vq=∑i=1qvi−∑i=1q−1vi=fS(Vq)−∑i=1q−1vi≥∑i=1qv~i−∑i=1q−1vid_S(q)· s_q≥ v_q= _i=1^qv_i- _i=1^q-1v_i=f_S(V_q)- _i=1^q-1v_i≥ _i=1^q v_i- _i=1^q-1v_i. Condition (iv) holds for any i since the total value up to index i is the same as an existing valid partition. Thus, the new cost and value sequences form a valid partition. The total value of the new partition is the same as ∑i=1nv~i _i=1^n v_i, but the total cost of the new partition is lower than ∑i=1ns~i _i=1^n s_i, contradicting that s~1,s~2,…,s~n s_1, s_2,…, s_n have the lowest total cost among all valid partitions. If s~q<sq s_q<s_q, we can also construct a new valid partition contradicting the selection of s~1,s~2,…,s~n s_1, s_2,…, s_n. Notice that ∑i=1q−1vi=∑i=1q−1dS(i)⋅si=∑i=1q−1dS(i)⋅s~i≥∑i=1q−1v~i _i=1^q-1v_i= _i=1^q-1d_S(i)· s_i= _i=1^q-1d_S(i)· s_i≥ _i=1^q-1 v_i, where the first equality follows from the definition of Λ2(S) ^2(S) and the inequality follows from condition (i) of Definition 1. Hence, fS(Vq)−∑i=1q−1v~i f_S(V_q)- _i=1^q-1 v_i ≥fS(Vq)−∑i=1q−1vi ≥ f_S(V_q)- _i=1^q-1v_i =fS(Vq)−fS(Vq−1) =f_S(V_q)-f_S(V_q-1) =dS∪Vq−1(q)⋅c(q) =d_S∪ V_q-1(q)· c(q) =dS(q)⋅sq =d_S(q)· s_q >dS(q)⋅s~q. >d_S(q)· s_q. Thus, condition (iv) has slack for i=qi=q in the assumed valid partition of v~ v. Together with s~q<sq s_q<s_q, it implies that s~q s_q can be increased without violating both conditions (i) and (iv) for i=qi=q. It can also be inferred that there is positive cost spent on at least one element in q+1,q+2,…,nq+1,q+2,…,n, because otherwise v~=∑i=1nv~i=∑i=1qv~i≤∑i=1qds(i)⋅s~i≤∑i=1qds(i)⋅si≤Λ2(S) v= _i=1^n v_i= _i=1^q v_i≤ _i=1^qd_s(i)· s_i≤ _i=1^qd_s(i)· s_i≤ ^2(S), contradicting that v~>Λ2(S) v> ^2(S). Let m be the lowest index larger than q satisfying s~m>0 s_m>0. If we move a small amount of cost ϵ>0ε>0 from s~m s_m to s~q s_q, v~q v_q can be increased by dS(q)⋅ϵd_S(q)·ε. On the other side, v~m v_m can be decreased by dS(q)⋅ϵd_S(q)·ε (which does not violate condition (i) for i=mi=m since dS(q)⋅ϵ≥dS(m)⋅ϵd_S(q)·ε≥ d_S(m)·ε). Meanwhile, condition (iv) is not violated for any q<i<mq<i<m because v~i=0 v_i=0 for all such i values. In this way, we have constructed a new valid partition of v~ v with higher cost spent on element q, contradicting that s~1,s~2,…,s~n s_1, s_2,…, s_n are the last cost sequence in the lexicographic order. We have identified a contradiction in every case and completed the proof. ∎ Appendix D Equivalence between the optimum of Equation (9) and Λ2(S) ^2(S) Lemma 6. For any value v that has a valid partition v1,v2,…,vnv_1,v_2,…,v_n, there exists an indicator vector =⟨x1,x2,…,xn⟩∈[0,1]nx= x_1,x_2,…,x_n ∈[0,1]^n that satisfies all the constraints of Equation 9 and ∑i∈V∖SfS(i)⋅xi=v _i∈ V Sf_S(i)· x_i=v. Proof. We set xi=vifS(i)x_i= v_if_S(i) for each element i∈V∖Si∈ V S, and xi=0x_i=0 for each element i∈Si∈ S. It is easy to observe that ∑i∈V∖SfS(i)⋅xi=v _i∈ V Sf_S(i)· x_i=v (recall that vi=0v_i=0 for each i∈Si∈ S in a valid partition). Now we proceed to check if the x constructed meets all the constraints of Equation 9. For the first constraint, for each element i∈Vi∈ V, ∑j=1ifS(j)⋅xj=∑j=1ivi≤fS(Vi), _j=1^if_S(j)· x_j= _j=1^iv_i≤ f_S(V_i), where the inequality is due to condition (iv) of Definition 1. Let the cost sequence of the valid partition be s1,s2,…,sns_1,s_2,…,s_n. For the second constraint, ∑i∈Vc(i)⋅xi=∑i=p+1nvidS(i)≤∑i=p+1nsi≤b. _i∈ Vc(i)· x_i= _i=p+1^n v_id_S(i)≤ _i=p+1^ns_i≤ b. where the two inequalities are due to conditions (i) and (i) of Definition 1. In addition, for each element i∈V∖Si∈ V S, 0≤xi=vifS(i)≤si⋅dS(i)fS(i)=sic(i)≤1,0≤ x_i= v_if_S(i)≤ s_i· d_S(i)f_S(i)= s_ic(i)≤ 1, where the second inequality is due to condition (i) of Definition 1 and the third inequality is due to the constraint si≤c(i)s_i≤ c(i) in Definition 1. ∎ Lemma 7. For each indicator vector =⟨x1,x2,…,xn⟩∈[0,1]nx= x_1,x_2,…,x_n ∈[0,1]^n that satisfies all the constraints of Equation 9, ∑i∈V∖SfS(i)⋅xi _i∈ V Sf_S(i)· x_i has a valid partition. Proof. Let si=c(i)⋅xis_i=c(i)· x_i and vi=fS(i)⋅xiv_i=f_S(i)· x_i. It is easy to observe that ∑i=1nvi=∑i=1nfS(i)⋅xi=∑i∈V∖SfS(i)⋅xi _i=1^nv_i= _i=1^nf_S(i)· x_i= _i∈ V Sf_S(i)· x_i. Now we proceed to check if viv_i and sis_i satisfy all the other conditions of a valid partition in Definition 1. For condition (i), ∑i=1nsi=∑i=1nc(i)⋅xi≤b, _i=1^ns_i= _i=1^nc(i)· x_i≤ b, where the inequality is due to the second constraint of Equation 9. For condition (i), for each element i∈Vi∈ V, dS(i)⋅si=fS(i)⋅xi=vi. d_S(i)· s_i=f_S(i)· x_i=v_i. For condition (iv), for each element i∈Vi∈ V, ∑j=1ivi=∑j=1ifS(j)⋅xj≤fS(Vi), _j=1^iv_i= _j=1^if_S(j)· x_j≤ f_S(V_i), where the inequality is due to the first constraint of Equation 9. Thus, all the conditions of Definition 1 are satisfied. So, ∑i∈V∖SfS(i)⋅xi _i∈ V Sf_S(i)· x_i has a valid partition. ∎ With Lemma 6 and Lemma 7, we can conclude that the optimum of Equation 9 is equal to the maximum value that has a valid partition, i.e., Λ2(S) ^2(S). Appendix E Λ3 ^3 in linear program presentation To write the calculation of Λ3 ^3 as a linear program, we can further add the removing item to Equation 9. max ∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi) _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i) (17) subject to ∀i∈V,∑j=1ifS(j)⋅xj≤fS(Vi), ∀ i∈ V, _j=1^if_S(j)· x_j≤ f_S(V_i), ∑i∈Vc(i)⋅xi≤b. _i∈ Vc(i)· x_i≤ b. The optimum of Equation 17 is equal to Λ3(S) ^3(S). This can be proved through a similar analysis to Appendix A. If the elements in V∖SV S are arranged in non-ascending order of marginal density with respect to S, it is easy to see that the optimum of the following linear program is equal to Λ2(S) ^2(S) defined in Equation 8: max ∑i∈V∖SfS(i)⋅xi _i∈ V Sf_S(i)· x_i (18) subject to ∑i∈Vc(i)⋅xi≤b, _i∈ Vc(i)· x_i≤ b, ∀i∈S,0≤xi≤1, ∀ i∈ S, 0≤ x_i≤ 1, ∀i∈V∖S,0≤xi≤fS∪Vi−1(i)fS(i). ∀ i∈ V S, 0≤ x_i≤ f_S∪ V_i-1(i)f_S(i). Thus, Equation 18 is a variation of calculating Λ2(S) ^2(S). If we add the removing item to this linear program, we can then get a variation of calculating Λ3(S) ^3(S) as follows: max ∑i∈V∖SfS(i)⋅xi−∑i∈SfV∖i(i)⋅(1−xi) _i∈ V Sf_S(i)· x_i- _i∈ Sf_V \i\(i)·(1-x_i) (19) subject to ∑i∈Vc(i)⋅xi≤b, _i∈ Vc(i)· x_i≤ b, ∀i∈S,0≤xi≤1, ∀ i∈ S, 0≤ x_i≤ 1, ∀i∈V∖S,0≤xi≤fS∪Vi−1(i)fS(i). ∀ i∈ V S, 0≤ x_i≤ f_S∪ V_i-1(i)f_S(i). Comparing Equation 19 with Equation 6, the only difference is the feasible range for xix_i where i∈V∖Si∈ V S. Similar to computing Λ1(S) ^1(S) based on Equation 6, we can compute Λ3(S) ^3(S) by picking elements greedily according to their “weights” in the objective function until the budget is fulfilled to get the optimum of Equation 19, where for each i∈Si∈ S, its weight is fV∖i(i)f_V \i\(i); for each i∈V∖Si∈ V S, its weight is fS(i)f_S(i). Consequently, the time complexity to compute Λ3(S) ^3(S) is also O(nlogn)=O(|V|log|V|)O(n n)=O(|V| |V|) due to the sorting of the elements, the same as Λ0(S) ^0(S), Λ1(S) ^1(S) and Λ2(S) ^2(S). Appendix F Experimental results for additional cost settings Figure 6 presents the approximation guarantees derived from different upper bounds for cost setting (b). We conduct experiments for all ground sets generated with different budgets from 20 to 50 (step size 1). So, for each data set, there are 620 problem instances (20 ground sets × 31 different budgets from 20 to 50). Following the recommendations in Section 4, our evaluation includes all enumerated augmentations Λ0+ ^0+, Λ1+ ^1+, Λ2+ ^2+, Λ3+ ^3+, and two unified augmentations Λ0∗ ^0*, Λ1∗ ^1*. Figure 7 presents the approximation guarantees derived from different upper bounds for cost setting (c). We conduct experiments for all ground sets generated with different budgets from 6 to 20 (step size 1). So, for each data set, there are 300 problem instances (20 ground sets × 15 different budgets from 6 to 20). (a) Adult Income (b) Caltech36 (c) ego-facebook (d) com-youtube Figure 6: Actual approximation guarantee plots for different upper bounds in cost setting (b) (a) Adult Income (b) Caltech36 (c) ego-facebook (d) com-youtube Figure 7: Actual approximation guarantee plots for different upper bounds in cost setting (c)