Indexed by:
Abstract:
The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this paper, we present four streaming algorithms for this problem by utilizing the concept of diminishing-return ratio. We analyze these algorithms to obtain the corresponding approximation ratios, which generalize the previous results for the submodular case. The numerical experiments show that our algorithms have better solution quality and competitive running time when compared to an existing algorithm.
Keyword:
Reprint Author's Address:
Email:
Source :
JOURNAL OF GLOBAL OPTIMIZATION
ISSN: 0925-5001
Year: 2019
Issue: 4
Volume: 76
Page: 729-743
1 . 8 0 0
JCR@2022
ESI Discipline: ENGINEERING;
ESI HC Threshold:136
JCR Journal Grade:1
Cited Count:
WoS CC Cited Count: 25
SCOPUS Cited Count: 29
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 5
Affiliated Colleges: