On Multiset Selection with Size Constraints

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

2018

THIRTY-SECOND AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTIETH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / EIGHTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE

1395-1402

New Orleans, LA, United states

2275 E BAYSHORE RD, STE 160, PALO ALTO, CA 94303 USA

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE

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 alpha(f) and beta(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(-beta f), (alpha(f)/2)(1 - e(-alpha f)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.

其他

英语

CPCI-S ; EI

Science and Technology Innovation Committee Foundation of Shenzhen[ZDSYS201703031748284]

Computer Science ; Engineering

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic

WOS:000485488901058

20190506436097

Artificial intelligence ; Iterative methods

Artificial Intelligence:723.4 ; Numerical Methods:921.6

Web of Science

1.Univ Sci & Technol China, Sch Comp Sci & Technol, Anhui Prov Key Lab Big Data Anal & Applicat, Hefei 230027, Anhui, Peoples R China
2.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen Key Lab Computat Intelligence, Shenzhen 518055, Peoples R China

Qian, Chao,Zhang, Yibo,Tang, Ke,et al. On Multiset Selection with Size Constraints[C]. 2275 E BAYSHORE RD, STE 160, PALO ALTO, CA 94303 USA:ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE,2018:1395-1402.