收录:
摘要:
In the article, we devise streaming algorithms for maximization of a monotone submodular function subject to a cardinality constraint on the integer lattice. Based on the observation that lattice submodularity is not equivalent to diminishing return submodularity on the integer lattice but rather a weaker condition, we propose a one-pass streaming algorithm with a modified binary search as subroutine of each step. Finally, we show that the algorithm is with approximation ratio 1/2-epsilon, memory complexity O(epsilon-1klogk), and per-element query complexity O(epsilon-2log2k).
关键词:
通讯作者信息:
电子邮件地址:
来源 :
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
ISSN: 1532-0626
年份: 2021
期: 17
卷: 35
2 . 0 0 0
JCR@2022
ESI高被引阀值:87
JCR分区:3
归属院系: