Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2020
ISSN: 0302-9743
Year: 2020
Volume: 12337
Page: 193-204
Cited Count:
SCOPUS Cited Count: 2
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: