Contemporary Issues in Network Design

网络设计的当代问题

• 批准号: 0830519
• 负责人: David Williamson
• 金额: $ 15万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830519&HistoricalAwards=false
• 关键词: Contemporary; Issues; Network; Design

Problems in the design of low-cost networks are central to our understanding of algorithms. Computing a minimum-cost spanning tree is one of the first graph algorithms to be taught in any standard algorithms course; indeed, the minimum-cost spanning tree algorithm of Boruvka is one of the earliest graph algorithms known. In the last decade or so, similar advances in our understanding of approximation algorithms have occurred through research into generalizations of the minimum-cost spanning tree problem and the Steiner tree problem. This research will consider more recent issues in the low-cost design of networks, and to discover similar, general algorithmic techniques to address them.One central issue now under consideration is that of the role of uncertainty in the specification of the design of the network. One of the ways this is done is by considering a probability distribution over the potential connectivity requirements, leading to stochastic optimization problems; another is that of giving a universal solution, from which a good solution can be derived no matter what requirements are realized. Most prior work in the area assumed that network connections would be purchased, but recent work in infrastructure leasing considers issues in which connectivity requirements are satisfied for shorter periods of time by leasing connectivity from another party instead of building a network.Finally, recent work has considered the general problem of dropping connectivity requirements in the case that they become too expensive to fulfill. This has been explored in simple cases in the past of the prize-collecting Steiner tree problem, but more general models have only recently started to be considered. The intellectual merit of the research lies in finding significant methodological innovations in the course of addressing these issues, and finding simpler, better, more general, and more practical approximation algorithms as a result of this research.Network design problems are increasingly important in a society where reliable communication is essential. In many situations, there is uncertainty about the inputs on which you must compute, since, for example, it is hard to detect failed links and exact network speeds are volatile. If successful, this research will lead to algorithms that can deal with the uncertainty inherent in real-world networks.

低成本网络设计中的问题是我们理解算法的核心。 计算最小成本生成树是任何标准算法课程中要教授的第一个图算法之一;事实上，Boruvka的最小成本生成树算法是已知的最早的图算法之一。 在过去的十年左右，类似的进步，我们的理解近似算法已经发生了通过研究到推广的最小成本生成树问题和斯坦纳树问题。这项研究将考虑最近的问题，在低成本的网络设计，并发现类似的，一般的算法技术来解决them.One中心问题，现在正在考虑的是，在网络的设计规范的不确定性的作用。 其中一种方法是考虑潜在连接需求的概率分布，从而导致随机优化问题;另一种方法是给出一个通用的解决方案，无论实现什么要求，都可以从中导出一个好的解决方案。 在该领域的大多数先前的工作假设网络连接将被购买，但最近的工作在基础设施租赁考虑的问题，其中的连接要求，满足较短的时间内从另一方租赁连接，而不是建立一个网络。最后，最近的工作已经考虑了一般的问题，放弃连接要求的情况下，他们变得过于昂贵，以满足。 在过去的获奖Steiner树问题中，这已经在简单的情况下进行了探索，但直到最近才开始考虑更一般的模型。 的研究的智力价值在于发现在解决这些问题的过程中显着的方法创新，并找到更简单，更好，更一般，更实用的近似算法作为本research.Network设计问题是越来越重要的社会中，可靠的通信是必不可少的。在许多情况下，您必须计算的输入存在不确定性，例如，很难检测到故障链路，并且确切的网络速度不稳定。 如果成功，这项研究将导致能够处理现实世界网络中固有的不确定性的算法。