Indexed by:
Abstract:
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).
Keyword:
Reprint Author's Address:
Email:
Source :
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
ISSN: 1532-0626
Year: 2021
Issue: 17
Volume: 35
2 . 0 0 0
JCR@2022
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:87
JCR Journal Grade:3
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 9
Affiliated Colleges: