收录:
摘要:
We study the submodular maximization problem in generalized streaming setting using a two-stage policy. In the streaming context, elements are released in a fashion that an element is revealed at one time. Subject to a limited memory capacity, the problem aims to sieve a subset of elements with a sublinear size l, such that the expecting objective value of all utility functions over the summarized subsets has a performance guarantee. We present a generalized one pass, (gamma(5)(min)/(5 + 2 gamma(2)(min)) - O(is an element of))-approximation, which consumes O(is an element of(-1) l log(l gamma(-1)(min))) memory and runs in O(is an element of(-1) kmn log(l gamma(-1)(min))) time, where k, n, m and gamma(min) denote the cardinality constraint, the element stream size, the amount of the learned functions, and the minimum generic submodular ratio of the learned functions, respectively.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2020
ISSN: 0302-9743
年份: 2020
卷: 12337
页码: 193-204
归属院系: