On Multiset Selection With Size Constraints

This paper considers the multiset selection problem with size constraints, which arises in many real-world applications such as budget allocation. Previous studies required the objective function f to be submodular, while we relax this assumption by introducing the notion of the submodularity ratios (denoted by αf and βf ). We propose an anytime randomized iterative approach POMS, which maximizes the given objective f and minimizes the multiset size simultaneously. We prove that POMS using a reasonable time achieves an approximation guarantee of max{1 − e−βf, (αf /2)(1 − e−αf )}. Particularly, when f is submdoular, this bound is at least as good as that of the previous greedy-style algorithms. In addition, we give lower bounds on the submodularity ratio for the objectives of budget allocation. Experimental results on budget allocation as well as a more complex application, namely, generalized influence maximization, exhibit the superior performance of the proposed approach.

Authors

• Chao Qian School of Artificial Intelligence, Nanjing University, Nanjing 210023, China
• Yibo Zhang National University of Defense Technology
• Ke Tang Southern University of Science and Technology
• Xin Yao Lingnan University

Keywords

No keywords are indexed for this paper.