收录:
摘要:
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 (1 - 1/e - epsilon) and O (log n/epsilon(2)) 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 (1 - 1/e - epsilon)approximation in O (log(2) m log n/epsilon(4)) 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 (1 - e(-gamma 2) - epsilon) , runs in O (log n/epsilon(2)) adaptive rounds and requires O ((n log n/epsilon(2))) queries, where gamma is the Continuous generic submodularity ratio.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
COMPUTING AND COMBINATORICS (COCOON 2020)
ISSN: 0302-9743
年份: 2020
卷: 12273
页码: 520-531
归属院系: