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 (Figure presented.), memory complexity (Figure presented.), and per-element query complexity (Figure presented.). © 2021 John Wiley & Sons Ltd.
Keyword:
Reprint 's Address:
Email:
Source :
ISSN: 1532-0626
Year: 2023
Issue: 17
Volume: 35
Language: English
1 . 5
JCR@2023
1 . 5 0 0
JCR@2023
ESI HC Threshold:32
JCR Journal Grade:2
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: