Indexed by:
Abstract:
Many real-world applications arising from social networks, personalized recommendations, and others, require extracting a relatively small but broadly representative portion of massive data sets. Such problems can often be formulated as maximizing a monotone set function with cardinality constraints. In this paper, we consider a streaming model where elements arrive quickly over time, and create an effective, and low-memory algorithm. First, we provide the first single-pass linear-Time algorithm, which is a a deterministic algorithm, achieves an approximation ratio of [ γ4 a(1+γ+γ2+γ3)-] for any ≥ 0 with a query complexity of n/ + a and a memory complexity of O(aklog(k)log(1/)), where a is a positive integer and γ is the submodularity ratio. However, the algorithm may produce less-Than-ideal results. Our next result is to describe a multi-streaming algorithm, which is the first deterministic algorithm to attain an approximation ratio of 1-e-γ-with linear query complexity. © 2023 World Scientific Publishing Company.
Keyword:
Reprint Author's Address:
Email:
Source :
International Journal of Foundations of Computer Science
ISSN: 0129-0541
Year: 2023
Issue: 6
Volume: 35
Page: 631-650
0 . 8 0 0
JCR@2022
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:19
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 8
Affiliated Colleges: