收录:
摘要:
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, such that the expecting objective value of all utility functions over the summarized subsets has a performance guarantee. We present a generalized one pass, -approximation, which consumes memory and runs in time, where k, n, m and 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. © 2020, Springer Nature Switzerland AG.
关键词:
通讯作者信息:
电子邮件地址: