On multiset selection with size constraints

Qian，Chao1; Zhang，Yibo1; Tang，Ke2; Yao，Xin2

2018

32nd AAAI Conference on Artificial Intelligence, AAAI 2018

1395-1402

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 α and β ). 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 , (α /2)(1 − e )}. 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.

其他

英语

2-s2.0-85057227772

Scopus

1.Anhui Province Key Lab of Big Data Analysis and Application, School of Computer Science and Technology, University of Science and Technology of China, ,Hefei,230027,China
2.Shenzhen Key Lab of Computational Intelligence, Department of Computer Science and Engineering, Southern University of Science and Technology, ,Shenzhen,518055,China

Qian，Chao,Zhang，Yibo,Tang，Ke,et al. On multiset selection with size constraints[C],2018:1395-1402.