An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
复制标题
DOI：
10.1145/3313276.3316304
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
中科院分区：
文献类型：
--
作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
本文研究了自适应复杂性模型中拟阵约束下的次模最大化问题。该模型最近被引入到子模块优化的背景下，以量化并行计算模型中黑盒优化的信息理论复杂性。非正式地，算法的自适应性是当每一轮可以并行执行多项式多个函数求值时，它所进行的顺序轮数。由于子模块优化经常应用于大型数据集，我们寻求具有低适应性的算法，以通过并行化实现加速。因此，最近的工作一直致力于设计常数因子近似算法最大化子模函数在各种约束下的自适应复杂性模型。尽管在自适应复杂性模型的子模最大化工作的爆发，最大化一个单调的子模函数在拟阵约束下的基本问题仍然难以捉摸。特别是，所有已知的技术都失败了这个问题，也没有已知的常数因子近似算法，其自适应性是次线性的秩的拟阵k或在最坏的情况下次线性的大小的地面集n。本文给出了自适应复杂度模型中拟阵约束下单调子模函数最大化问题的一个近似算法。该算法的近似保证是任意接近最优的1−1/e，并且它具有近似最优的自适应性<$log（log（n）log（k））。这一结果是使用一种新的技术，自适应排序，从以前的子模块最大化的自适应复杂性模型的技术出发。除了我们的主要结果，我们展示了如何使用这种技术来设计其他近似算法具有强大的近似保证和多对数自适应。
In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. Consequently, a recent line of work has been devoted to designing constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid k or in the worst case sublinear in the size of the ground set n. In this paper we present an approximation algorithm for the problem of maximizing a monotone submodular function under a matroid constraint in the adaptive complexity model. The approximation guarantee of the algorithm is arbitrarily close to the optimal 1−1/e and it has near optimal adaptivity of Ø(log(n)log(k)). This result is obtained using a novel technique of adaptive sequencing which departs from previous techniques for submodular maximization in the adaptive complexity model. In addition to our main result we show how to use this technique to design other approximation algorithms with strong approximation guarantees and polylogarithmic adaptivity.