论文标题
可扩展的分布式算法，用于MAPREDUCE和自适应复杂度模型中的尺寸约束的supprodular suppodular算法
Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models
论文作者
论文摘要
MAPREDUCE（MR）模型中的下二个功能的分布最大化已引起了很多关注，最终在两个框架中达到了允许在MR设置中运行的集中式算法而不会损失近似值，只要集中式算法就可以满足一定的一致性 - 以前只能通过标准的贪婪和连续的Greedy Algsy Algy Algy Algy Algs groudementions满足一定的一致性。单独的工作线研究了自适应复杂度模型中的亚辅导最大化的并行性，在该模型中，每个线程都可以访问整个接地集。为了使单调和下一个功能的尺寸约束最大化，我们表明几种均方根自适应（高度可行的）算法满足在MR设置中工作所需的一致性属性，从而产生实用，可行的和分布的算法。另外，我们针对此问题开发了具有线性查询复杂性的第一个分布式算法。最后，我们提供了一种以其他MR回合为代价的MR算法的最大基数约束的方法。
Distributed maximization of a submodular function in the MapReduce (MR) model has received much attention, culminating in two frameworks that allow a centralized algorithm to be run in the MR setting without loss of approximation, as long as the centralized algorithm satisfies a certain consistency property -- which had previously only been known to be satisfied by the standard greedy and continous greedy algorithms. A separate line of work has studied parallelizability of submodular maximization in the adaptive complexity model, where each thread may have access to the entire ground set. For the size-constrained maximization of a monotone and submodular function, we show that several sublinearly adaptive (highly parallelizable) algorithms satisfy the consistency property required to work in the MR setting, which yields practical, parallelizable and distributed algorithms. Separately, we develop the first distributed algorithm with linear query complexity for this problem. Finally, we provide a method to increase the maximum cardinality constraint for MR algorithms at the cost of additional MR rounds.
