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 的最小成本生成树算法是已知最早的图算法之一。 在过去十年左右的时间里，通过研究最小成本生成树问题和斯坦纳树问题的推广，我们对近似算法的理解也取得了类似的进步。这项研究将考虑网络低成本设计中的最新问题，并发现类似的通用算法技术来解决这些问题。现在正在考虑的一个中心问题是不确定性在网络设计规范中的作用。 实现此目的的方法之一是考虑潜在连接要求的概率分布，从而导致随机优化问题；另一个是给出一个通用的解决方案，无论实现什么需求都可以从中导出一个好的解决方案。 该领域的大多数先前工作都假设将购买网络连接，但基础设施租赁方面的最新工作考虑了通过从另一方租赁连接而不是构建网络来在较短的时间内满足连接要求的问题。考虑了在连接要求变得过于昂贵而无法满足的情况下放弃连接要求的普遍问题。 在过去的获奖斯坦纳树问题的简单案例中已经对此进行了探索，但最近才开始考虑更通用的模型。 这项研究的智力价值在于在解决这些问题的过程中发现了重大的方法创新，并通过这项研究找到了更简单、更好、更通用、更实用的近似算法。网络设计问题在社会中越来越重要可靠的通信至关重要。在许多情况下，您必须计算的输入存在不确定性，因为例如很难检测到故障链路，并且确切的网络速度不稳定。 如果成功，这项研究将产生能够处理现实世界网络固有的不确定性的算法。