次模函数最大化的流算法综述

次模函数优化在计算机科学、数学、经济学等学科得到广泛研究.大数据环境下的次模优化是相对较新的研究领域，受到更多关注.特别地，考虑基于流模型的次模最大化问题.在该问题中，数据以流的形式呈现，其目的是从数据流中抽取满足某些特性的稀疏子集，最大化次模收益函数值.介绍了基于流模型的次模最大化问题的阈值和优先权方法，同时也介绍了若干次模最大化变形的流算法进展.

A survey on streaming algorithms for maximizing submodular functions

While submodular function optimization has been studied extensively in computer science, mathematics, and economics, etc., submodular optimization in big data environment is a relatively new field that has attracted many attentions recently. In particular, submodular optimization with streaming data is the focus of this work. Facing real-time streaming data revealed in real time, the goal is to select a sparse subset satisfying certain desirable features from the stream to maximize certain submodular utility function. The main purpose of this paper is to provide suggestions for future research on this important class of problems. We introduce the threshold and preemption methods for the streaming submodular maximization problem. We also investigate the development of streaming algorithms for some variants of submodular maximization problems.