Indexed by:
Abstract:
Emerging applications such as optimal budget allocation and sensor placement impose problems of maximizing variants of submodular functions with constraints under a streaming setting. In this paper, we first devise a streaming algorithm based on Sieve-Streaming for maximizing a monotone diminishing return submodular (DR-submodular) function with a cardinality constraint on the integer lattice and show it is a one-pass algorithm with approximation ratio 1/2 - epsilon. The key idea to ensure one pass for the algorithm is to combine binary search for determining the level of an element with the exponential-growth method for estimating the OPT. Inspired by Sieve-Streaming++, we then improve the memory of the algorithm to O(k/epsilon) and the query complexity to O(k log(2) k/epsilon).
Keyword:
Reprint Author's Address:
Email:
Source :
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
ISSN: 0217-5959
Year: 2021
Issue: 05
Volume: 38
1 . 4 0 0
JCR@2022
ESI Discipline: ENGINEERING;
ESI HC Threshold:87
JCR Journal Grade:4
Cited Count:
WoS CC Cited Count: 4
SCOPUS Cited Count: 6
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: