Indexed by:
Abstract:
In this paper, we present an adaptive algorithm for maximizing a monotone nonsubmodular function with a cardinality constraint. Based on the relationship between OPT and the maximum marginal gain of the elements in the ground set, the algorithm first calculates all possible values of OPT, then computes in parallel a family of sets each of which corresponding to each value of OPT, and lastly selects the set with maximum value as the desired solution. For the first, we divide the value range of OPT into finite parts and take the lower bound of each part as a possible value of OPT. As the main ingredient for the parallel computation, we use the Bernoulli distribution to independently sample elements so as to ensure further parallelism. Provided the generic submodularity ratio (Formula Presented) of the monotone set function, we prove the algorithm deserves an approximation ratio (Formula Presented), consumes (Formula Presented) adaptive rounds, and needs (Formula Presented) oracle queries in expectation. Moreover, if the set function is submodular (i. e. (Formula Presented)), our algorithm can achieve an approximation guarantee (Formula Presented) coinciding with the state-of-art result. © 2020, Springer Nature Switzerland AG.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2020
Volume: 12290 LNCS
Page: 195-203
Language: English
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 2
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 13
Affiliated Colleges: