收录:
摘要:
In the paper, we study the adaptivity of maximizing a monotone nonsubmodular function subject to a cardinality constraint. Adaptive approximation algorithm has been previously developed for the similar constrained maximization problem against submodular function, attaining an approximation ratio of and rounds of adaptivity. For more general constraints, Chandra and Kent described parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to either cardinality or packing constraints, achieving a near-optimal-approximation in rounds. We propose an Expand-Parallel-Greedy algorithm for the multilinear relaxation of a monotone and normalized set function subject to a cardinality constraint based on rounding the multilinear relaxation of the function. The algorithm achieves a ratio of, runs in adaptive rounds and requires queries, where is the Continuous generic submodularity ratio. © 2020, Springer Nature Switzerland AG.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
ISSN: 0302-9743
年份: 2020
卷: 12273 LNCS
页码: 520-531
语种: 英文
归属院系: