收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
ISSN: 1865-0929
年份: 2021
卷: 1362
页码: 58-67
语种: 英文
归属院系: