Streaming k-Submodular Maximization under Noise subject to Size Constraint
Streaming k-Submodular Maximization under Noise subject to Size Constraint
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Lan N. Nguyen;M. Thai
中科院分区：
文献类型：
--
作者：
Lan N. Nguyen;M. Thai
具有大小约束的k -次模函数的极大化问题近年来受到了广泛的关注.在本文中，我们研究了这个问题的一个更现实的场景，即（1）获得目标函数的精确评估是不切实际的，相反，它的噪声版本被获取;（2）算法只需要在数据集上进行一次遍历，及时产生解决方案。我们提出了两个新的流媒体算法，即DS TREAM和RS TREAM，其理论性能保证。我们进一步证明了我们的算法在两个应用程序中的效率，即Inquirience Maximization和Sensor Placement，表明我们的算法可以将比较结果返回给最先进的非流方法，同时使用更少的查询次数。
Maximizing on k -submodular functions subject to size constraint has received extensive attention recently. In this paper, we investigate a more realistic scenario of this problem that (1) obtaining exact evaluation of an objective function is impractical, instead, its noisy version is acquired; and (2) algorithms are required to take only one single pass over dataset, producing solutions in a timely manner. We propose two novel streaming algorithms, namely DS TREAM and RS TREAM , with their theoretical performance guarantees. We further demonstrate the efficiency of our algorithms in two applications in Influence Maximization and Sensor Placement, showing that our algorithms can return comparative results to state-of-the-art non-streaming methods while using a much fewer number of queries.