Indexed by:
Abstract:
In the paper, we design an adaptive algorithm for non-submodular set function maximization over a single matroid constraint. We measure the deviation of the set function from fully submodular with the help of the generic submodularity ratio gamma. The adaptivity quantifies the information theoretic complexity of oracle optimization for parallel computations. We propose a new approximation algorithm based on the continuous greedy approach and prove that the algorithm could obtain a fractional solution with approximation ratio (1 - e(-gamma 2) - O(epsilon)) in O(log n log(k/gamma epsilon)/epsilon(-2) log n log(1/gamma) - epsilon(-1) log(1-epsilon)) then use the contention resolution schemes to convert the fractional solution to a discrete one with gamma (1 - e(-1))(1 - e(-gamma 2) - O(epsilon))-approximation.
Keyword:
Reprint Author's Address:
Email:
Source :
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
ISSN: 1547-5816
Year: 2022
Issue: 3
Volume: 19
Page: 2050-2070
1 . 3
JCR@2022
1 . 3 0 0
JCR@2022
ESI Discipline: ENGINEERING;
ESI HC Threshold:49
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 12
Affiliated Colleges: