Indexed by:
Abstract:
Nowadays, massive amounts of data are growing at a rapid rate every moment. If data can be processed and analyzed promptly as they arrive, they can bring huge added values to the society. In this paper, we consider the problem of maximizing a monotone non-submodular function subject to a cardinality constraint under the streaming setting and present a linear-time single-pass deterministic algorithm for this problem. We analyze the algorithm using the parameter of the generic submodularity ratio gamma to achieve an approximation ratio of [gamma(4)/c(1+gamma+gamma(2)+gamma(3)) - epsilon] for any epsilon >= 0 with the query complexity [n/c] + c, and the memory complexity is O(ck log(k) log(1/epsilon)), where c is a positive integer. When gamma = 1, the algorithm achieves the same ratio for the submodular version of the problem with the matching query complexity and memory complexity.
Keyword:
Reprint Author's Address:
Source :
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021
ISSN: 0302-9743
Year: 2021
Volume: 13135
Page: 96-110
Cited Count:
WoS CC Cited Count: 0
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: