• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Association for Computing Machinery symposium on parallelism in algorithms and architectures >Fast Greedy Algorithms in MapReduce and Streaming
【24h】

Fast Greedy Algorithms in MapReduce and Streaming

机译：MapReduce和Streaming中的快速贪婪算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Greedy algorithms are practitioners' best friends-they are intuitive, simple to implement, and often lead to very good solutions. However, implementing greedy algorithms in a distributed setting is challenging since the greedy choice is inherently sequential, and it is not clear how to take advantage of the extra processing power. Our main result is a powerful sampling technique that aids in parallelization of sequential algorithms. We then show how to use this primitive to adapt a broad class of greedy algorithms to the MapReduce paradigm; this class includes maximum cover and submodular maximization subject to p-system constraints. Our method yields efficient algorithms that run in a logarithmic number of rounds, while obtaining solutions that are arbitrarily close to those produced by the standard sequential greedy algorithm. We begin with algorithms for modular maximization subject to a ma-troid constraint, and then extend this approach to obtain approximation algorithms for submodular maximization subject to knapsack or p-system constraints. Finally, we empirically validate our algorithms, and show that they achieve the same quality of the solution as standard greedy algorithms but run in a substantially fewer number of rounds.
机译：贪婪的算法是从业者的“最好的朋友 - 他们是直观的，实现的简单，并且经常导致非常好的解决方案。然而，由于贪婪选择本质上是顺序，在分布式设置中实现贪婪算法是具有挑战性的，并且目前尚不清楚如何利用额外的处理能力。我们的主要结果是一种强大的采样技术，有助于顺序算法的并行化。然后，我们展示如何使用这一原语来使广泛的贪婪算法适应MapReduce范式;此类包括P-System约束的最大覆盖和子模块最大化。我们的方法产生了在对数次数中运行的有效算法，同时获得任意接近标准顺序贪婪算法产生的解决方案。我们首先进行MA-TROID约束的模块化最大化算法，然后扩展这种方法，以获得对皮卡求或P系统约束的子模块最大化的近似算法。最后，我们经验验证了我们的算法，并表明它们与标准贪婪算法相同的解决方案质量，但在基本上更少的轮次运行。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号