Non-monotone Submodular Maximization in Exponentially Fewer Iterations
Non-monotone Submodular Maximization in Exponentially Fewer Iterations
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Eric Balkanski;Adam Breuer;Yaron Singer
中科院分区：
文献类型：
--
作者：
Eric Balkanski;Adam Breuer;Yaron Singer
在本文中，我们考虑了可以表达目标的应用程序的并行化，以最大程度地提高非单调性函数在基数约束下。我们的主要结果是一种算法，其近似值在O（log^2 n）自适应弹中任意接近1/2e，其中n是地面集的大小。这是在任何先前研究的算法上，对于受约束的非单调子模块最大化的任何先前研究的算法，这是指数的加速。除了可证明的保证，该算法在实践中的表现良好。具体而言，有关流量监控和个性化数据摘要应用程序的实验表明，该算法找到了其值与最新算法竞争的解决方案，而在较少的并行迭代中运行时，其值。
In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily close to 1/2e in O(log^2 n) adaptive rounds, where n is the size of the ground set. This is an exponential speedup in parallel running time over any previously studied algorithm for constrained non-monotone submodular maximization. Beyond its provable guarantees, the algorithm performs well in practice. Specifically, experiments on traffic monitoring and personalized data summarization applications show that the algorithm finds solutions whose values are competitive with state-of-the-art algorithms while running in exponentially fewer parallel iterations.