收录:
摘要:
In this paper, we study the problem of maximizing a sequence submodular function in the streaming setting, where the utility function is defined on sequences instead of sets of elements. We encode the sequence submodular maximization with a weighted digraph, in which the weight of a vertex reveals the utility value in selecting a single element and the weight of an edge reveals the additional profit with respect to a certain selection sequence. The edges are visited in a streaming fashion and the aim is to sieve a sequence of at most k elements from the stream, such that the utility is maximized. In this work, we present an edge-based threshold procedure, which makes one pass over the stream, attains an approximation ratio of (1 / (2 Δ+ 1) - O()) , consumes O(kΔ/ ) memory source in total and O(log (kΔ) / ) update time per edge, where Δ is the minimum of the maximal outdegree and indegree of the directed graph. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
关键词:
通讯作者信息:
电子邮件地址: