子模最大化的FAST算法

作者：Adam Breuer,Eric Balkanski,Yaron Singer

摘要：在本文中，我们描述了一种称为快速自适应排序技术（FAST）的新算法，用于在基数约束下最大化单调子模块函数，其近似比任意接近1-1 / e，isO（log（n）log2（logk））自适应，并使用总共o（nloglog（k））查询。最近的算法在渐近最坏情况分析方面具有可比较的保证，但是它们的实际轮数和查询复杂度在精度和置信度方面取决于非常大的常数和多项式，使得它们对于大数据集是不实际的。我们的主要贡献是在非渐近最坏情况查询复杂性和轮次数以及实际运行时方面都非常有效的设计。我们表明，该算法优于我们所知道的任何子模块最大化算法，包括通过在大型数据集上运行实验，对现有技术的串行算法进行超优化并行版本。这些实验表明，FAST比现有技术快几个数量级。

原文标题：The FAST Algorithm for Submodular Maximization

原文摘要：In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraintkwhose approximation ratio is arbitrarily close to1−1/e, isO(log(n)log2(logk))adaptive, and uses a total ofO(nloglog(k))queries. Recent algorithms have comparable guarantees in terms of asymptotic worst case analysis, but their actual number of rounds and query complexity depend on very large constants and polynomials in terms of precision and confidence, making them impractical for large data sets. Our main contribution is a design that is extremely efficient both in terms of its non-asymptotic worst case query complexity and number of rounds, and in terms of its practical runtime. We show that this algorithm outperforms any algorithm for submodular maximization we are aware of, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets. These experiments show FAST is orders of magnitude faster than the state-of-the-art.

地址：https://arxiv.org/abs/1907.06173