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 − 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.
Original language | English |
---|---|
Title of host publication | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 |
Publisher | AAAI press |
Pages | 1395-1402 |
Number of pages | 8 |
ISBN (Print) | 9781577358008 |
Publication status | Published - 2018 |
Externally published | Yes |
Bibliographical note
Publisher Copyright:Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Funding
This work was supported by the National Key Research and Development Program of China (2017YFB1003100, 2017YFB1003102), the NSFC (61603367, 61672478), the YESS (2016QNRC001) and the Science and Technology Innovation Committee Foundation of Shenzhen (ZDSYS201703031748284). Copyright ©c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.