收录:
摘要:
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 Delta+ 1) - O(epsilon)), consumes O(k Delta/epsilon) memory source in total and O(log(k Delta)/epsilon) update time per edge, where. is the minimum of the maximal outdegree and indegree of the directed graph.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN: 1382-6905
年份: 2020
期: 1
卷: 41
页码: 43-55
1 . 0 0 0
JCR@2022
ESI学科: MATHEMATICS;
ESI高被引阀值:46
归属院系: