收录:
摘要:
In this paper, we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular (DR-submodular) function and a nonnegative linear function on the integer lattice. As it is almost unapproximable for maximizing a submodular function without the condition of nonnegative, we provide weak (bifactor) approximation algorithms for this problem in two online settings, respectively. For the unconstrained online model, we combine the ideas of single-threshold greedy, binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation ratio. For the online streaming model subject to a cardinality constraint, we provide a one-pass (3-5)/2 weak approximation ratio streaming algorithm. Its memory complexity is (klogk/Ε), and the update time for per element is (log2k/Ε). © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2022.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
Journal of the Operations Research Society of China
ISSN: 2194-668X
年份: 2024
期: 3
卷: 12
页码: 795-807
归属院系: