Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2021
Volume: 12606 LNCS
Page: 362-370
Language: English
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 3
Affiliated Colleges: