Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
COMPUTING AND COMBINATORICS (COCOON 2020)
ISSN: 0302-9743
Year: 2020
Volume: 12273
Page: 520-531
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: