Indexed by:
Abstract:
Maximization of non-negative monotone submodular set functions under a knapsack constraint have been extensively studied in the last decade. Here, we consider the streaming algorithms of this problem on the integer lattice, or on a multi-set equivalently. This is more realistic for many practical problems such as sensor location and influence maximization. It is well known that submodularity and diminishing return submodularity are not equivalent on the integer lattice. We mainly focus on maximizing the diminishing return submodular (DR-submodular) functions with knapsack constraint on the integer lattice. Finally, by utilizing the binary search algorithm as a subroutine, we design an online streaming algorithm called DynamicMRT. Furthermore, we prove that it is a (1 / 3 - Ε) -approximation algorithm with O(Klog K) memory complexity and O(log K) query complexity per element. © 2021, Springer Nature Singapore Pte Ltd.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 1865-0929
Year: 2021
Volume: 1362
Page: 58-67
Language: English
Cited Count:
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 10
Affiliated Colleges: