On Multiset Selection With Size Constraints

Authors

  • Chao Qian University of Science and Technology of China
  • Yibo Zhang University of Science and Technology of China
  • Ke Tang Southern University of Science and Technology
  • Xin Yao Southern University of Science and Technology

Abstract

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-1/e^(β_f), (α_f/2)(1-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.

Downloads

Published

2018-04-25

How to Cite

Qian, C., Zhang, Y., Tang, K., & Yao, X. (2018). On Multiset Selection With Size Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11524

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization