论文标题
在$ K $ -SET系统约束下流式传输次管
Streaming Submodular Maximization under a $k$-Set System Constraint
论文作者
论文摘要
在本文中，我们提出了一个新颖的框架，该框架将单调量子次传输最大化的流算法转换为非单词酮suplodular最大化的流算法。这种减少很容易导致当前最紧密的确定性近似值率，但要受到$ k $ - 摩尔匹配的约束。此外，我们提出了第一个用于单调supsodular最大化的流算算法，约为$ k $伸缩性和$ k $ set的系统约束。加上我们提出的减少，我们获得了$ O（k \ log k）$和$ o（k^2 \ log k）$（k^2 \ log k）$近似比分别受上述约束约束。我们在一系列实验中广泛评估了算法对现有工作的经验性能，包括在随机生成的图中找到最大独立设置，从而最大程度地提高了社交网络上的线性功能，电影推荐，Yelp位置摘要以及Twitter数据摘要。
In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximization. This reduction readily leads to the currently tightest deterministic approximation ratio for submodular maximization subject to a $k$-matchoid constraint. Moreover, we propose the first streaming algorithm for monotone submodular maximization subject to $k$-extendible and $k$-set system constraints. Together with our proposed reduction, we obtain $O(k\log k)$ and $O(k^2\log k)$ approximation ratio for submodular maximization subject to the above constraints, respectively. We extensively evaluate the empirical performance of our algorithm against the existing work in a series of experiments including finding the maximum independent set in randomly generated graphs, maximizing linear functions over social networks, movie recommendation, Yelp location summarization, and Twitter data summarization.
