收录:
摘要:
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 [gamma(4)/a(1+gamma+gamma(2)+gamma(3)) - epsilon] for any epsilon >= 0 with a query complexity of inverted right perpendicularn/ainverted left perpendicular + a and a memory complexity of O(ak log(k) log(1/epsilon)), where a is a positive integer and gamma 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(- gamma) - epsilon with linear query complexity.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
ISSN: 0129-0541
年份: 2023
期: 06
卷: 35
页码: 631-650
0 . 8 0 0
JCR@2022
ESI学科: COMPUTER SCIENCE;
ESI高被引阀值:19
归属院系: