收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址: