• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Parallel and Distributed Computing and Networks >Scalable Parallel Algorithms for Difficult Combinatorial Problems: A Case Study in Optimization
【24h】

Scalable Parallel Algorithms for Difficult Combinatorial Problems: A Case Study in Optimization

机译：难求解组合问题的可扩展并行算法：以优化为例

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

摘要

A novel combination of emergent algorithmic methods, powerful computational platforms and supporting infrastructure is described. These complementary tools and technologies are used to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and two forms of parallel algorithms are devised and implemented. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. With the synergis-tic combination of techniques detailed here, it is now possible to solve problem instances that before were widely viewed as hopelessly out of reach. Target problems need only be amenable to reduction and decomposition. Applications are also discussed.
机译：描述了新兴算法方法，强大的计算平台和支持基础结构的新颖组合。这些互补的工具和技术用于对具有重要意义的组合问题发起系统的攻击。作为案例研究，计算了NP硬顶点覆盖问题的很大实例的最优解。为此，设计并实现了一种有效的顺序算法和两种形式的并行算法。事实证明，保持搜索空间的平衡分解对于实现可伸缩性至关重要。通过此处详细介绍的协同技术组合，现在可以解决以前被普遍认为无望地解决的问题实例。目标问题只需要还原和分解即可。还讨论了应用程序。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号