Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice
Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice
复制标题
DOI：
10.1142/s0217595921400042
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Zhenning Zhang;Longkun Guo;Yishui Wang;Dachuan Xu;Dongmei Zhang
中科院分区：
文献类型：
--
作者：
Zhenning Zhang;Longkun Guo;Yishui Wang;Dachuan Xu;Dongmei Zhang
最佳预算分配和传感器放置等新兴应用提出了在流设置下限制子模块函数变体最大化的问题。在本文中，我们首先设计了一种基于 Sieve-Streaming 的流算法，用于最大化具有整数格基数约束的单调递减收益子模（DR-子模）函数，并证明它是一种具有近似比的单遍算法[公式：参见文本]。确保算法一次通过的关键思想是将用于确定元素级别的二分搜索与用于估计 OPT 的指数增长方法结合起来。受Sieve-Streaming++的启发，我们将算法的内存提高到[公式：参见文本]，将查询复杂度提高到[公式：参见文本]。
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 [Formula: see text]. 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 [Formula: see text] and the query complexity to [Formula: see text].