• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the 25th ACM symposium on parallelism in algorithms and architectures >Fast Greedy Algorithms in MapReduce and Streaming
【24h】

Fast Greedy Algorithms in MapReduce and Streaming

机译：MapReduce和流媒体中的快速贪婪算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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系统约束的子模最大化。我们的方法产生了以对数轮数运行的有效算法，同时获得了与标准顺序贪婪算法产生的解任意接近的解。我们从受矩阵约束约束的模块最大化算法开始，然后扩展此方法以获得受背包或p系统约束的亚模最大化算法。最后，我们凭经验验证了我们的算法，并表明它们可以达到与标准贪婪算法相同的解决方案质量，但是轮回的数量要少得多。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号