On multiset selection with size constraints

Chao QIAN, Yibo ZHANG, Ke TANG, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

18 Citations (Scopus)

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. Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Original languageEnglish
Title of host publication32nd AAAI Conference on Artificial Intelligence, AAAI 2018
PublisherAAAI press
Pages1395-1402
Number of pages8
ISBN (Print)9781577358008
Publication statusPublished - 2018
Externally publishedYes

Bibliographical note

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.

Fingerprint

Dive into the research topics of 'On multiset selection with size constraints'. Together they form a unique fingerprint.

Cite this