首页> 外文期刊>IEEE/ACM Transactions on Networking >The Fast Heuristic Algorithms and Post-Processing Techniques to Design Large and Low-Cost Communication Networks
【24h】

The Fast Heuristic Algorithms and Post-Processing Techniques to Design Large and Low-Cost Communication Networks

机译:设计大型和低成本通信网络的快速启发式算法和后处理技术

获取原文
获取原文并翻译 | 示例

摘要

It is challenging to design large and low-cost communication networks. In this paper, we formulate this challenge as the prize-collecting Steiner Tree Problem (PCSTP). The objective is to minimize the costs of transmission routes and the disconnected monetary or informational profits. Initially, we note that the PCSTP is MAX SNP-hard. Then, we propose some post-processing techniques to improve suboptimal solutions to PCSTP. Based on these techniques, we propose two fast heuristic algorithms: the first one is a quasilinear time heuristic algorithm that is faster and consumes less memory than other algorithms; and the second one is an improvement of a state-of-the-art polynomial time heuristic algorithm that can find high-quality solutions at a speed that is only inferior to the first one. We demonstrate the competitiveness of our heuristic algorithms by comparing them with the state-of-the-art ones on the largest existing benchmark instances (169 800 vertices and 338 551 edges). Moreover, we generate new instances that are even larger (1 000 000 vertices and 10 000 000 edges) to further demonstrate their advantages in large networks. The state-of-the-art algorithms are too slow to find high-quality solutions for instances of this size, whereas our new heuristic algorithms can do this in around 6 to 45s on a personal computer. Ultimately, we apply our post-processing techniques to update the best-known solution for a notoriously difficult benchmark instance to show that they can improve near-optimal solutions to PCSTP. In conclusion, we demonstrate the usefulness of our heuristic algorithms and post-processing techniques for designing large and low-cost communication networks.
机译:设计大型且低成本的通信网络具有挑战性。在本文中,我们将此挑战表述为奖品收集斯坦纳树问题(PCSTP)。目的是使传输路径的成本和不连贯的金钱或信息利润最小化。最初,我们注意到PCSTP是MAX SNP硬的。然后,我们提出了一些后处​​理技术来改善PCSTP的次优解决方案。基于这些技术,我们提出了两种快速启发式算法:第一种是准线性时间启发式算法,与其他算法相比,该算法更快且消耗的内存更少;第二个是对最新多项式时间启发式算法的改进,该算法可以以仅次于第一个的速度找到高质量的解决方案。通过将其与最大的现有基准实例(169 800个顶点和338 551个边)上的最新算法进行比较,我们证明了我们的启发式算法的竞争力。此外,我们生成了更大的新实例(100万个顶点和10万个边),以进一步证明它们在大型网络中的优势。最新的算法太慢,无法为这种大小的实例找到高质量的解决方案,而我们的新启发式算法可以在个人计算机上大约6到45s内完成。最终,我们将后处理技术应用于一个非常困难的基准测试实例,以更新最著名的解决方案,以表明它们可以改善PCSTP的最佳解决方案。总之,我们证明了启发式算法和后处理技术对设计大型和低成本通信网络的有用性。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号