Submodular maximization problems belong to the family of combinatorial optimization problems and enjoy wide applications. In this paper, we focus on the problem of maximizing a monotone submodular function subject to a @math -knapsack constraint, for which we propose a streaming algorithm that achieves a @math -approximation of the optimal value, while it only needs one single pass through the dataset without storing all the data in the memory. In our experiments, we extensively evaluate the effectiveness of our proposed algorithm via two applications: news recommendation and scientific literature recommendation. It is observed that the proposed streaming algorithm achieves both execution speedup and memory saving by several orders of magnitude, compared with existing approaches.
Further, the authors in @cite_4 dealt with the case when @math and each entry of @math can take any positive values. Maximizing a monotone submodular function under a single knapsack constraint is also called a budgeted submodular maximization problem. This problem is also NP-hard, and the authors in @cite_0 suggested a greedy algorithm, which produces a @math -approximation of the optimal value with @math computation complexity. Specifically, it first enumerates all the subsets of cardinalities at most three, then greedily adds the elements with maximum marginal values per weight to every subset starting with three elements, and finally outputs the suboptimal subset. Although the solution has a @math -approximation guarantee, the @math computation cost prevents this greedy algorithm from being widely used in practice. Hence some modified versions of the greedy algorithm have been developed. The authors in @cite_4 applied it to document summarization with a @math performance guarantee. In @cite_9 , the so-called cost effective forward (CEF) algorithm for outbreak detection was proposed, which produces a solution with a @math -approximation guarantee and requires only @math computation complexity, where @math is the knapsack budget when @math .
@cite_0 @cite_9 @cite_4
2033885045 1962684803
In this paper, we obtain an (1-e^-^1)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n^5) function value computations. We treat the text summarization problem as maximizing a submodular function under a budget constraint. We show, both theoretically and empirically, a modified greedy algorithm can efficiently solve the budgeted submodular maximization problem near-optimally, and we derive new approximation bounds in doing so. Experiments on DUC'04 task show that our approach is superior to the best-performing method from the DUC'04 evaluation on ROUGE-1 scores.