收录:
摘要:
In this paper, we consider a streaming model of maximizing monotone lattice submodular function with a cardinality constraint on the integer lattice. As (lattice) submodularity does not imply the diminishing return property on the integer lattice, we introduce the Sieve-Streaming algorithm combining with a modified binary search subroutine to solve the problem. We also show it is with an approximation ratio 1 / 2 - , a memory complexity O(- 1klog k), and a query complexity O(- 2log2k) per element. © 2021, Springer Nature Switzerland AG.
关键词:
通讯作者信息:
电子邮件地址: