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的最低成本跨越树算法是已知的最早的图算法之一。 在过去的十年左右的时间里，我们对近似算法的理解的类似进展是通过研究对最小成本跨越树问题和施泰纳树问题的概括而发生的。这项研究将考虑网络低成本设计中的最新问题，并发现类似的，一般的算法技术来解决它们。现在正在考虑的一个中心问题是不确定性在网络设计规范中的作用。 这样做的方法之一是考虑对潜在连通性要求的概率分布，从而导致随机优化问题。另一个是提供通用解决方案，无论实现什么要求，都可以从中得出一个好的解决方案。 该地区的大多数先前工作都假定将购买网络连接，但是基础设施租赁的最新工作考虑了问题，即通过从另一方租赁连接而不是建立网络的连通性来满足较短时间的连接需求，而不是建立网络。最近的工作认为，在实现太昂贵的情况下，它们丢弃了连接性要求的一般问题，以至于他们变得昂贵。 在奖品收集的Steiner树问题的简单情况下，已经探讨了这一点，但直到最近才开始考虑更多的通用模型。 这项研究的智力优点在于在解决这些问题的过程中找到重要的方法论创新，并且由于这项研究而找到更简单，更好，更好，更一般，更实用的近似算法。在可靠交流至关重要的社会中，网络设计问题越来越重要。在许多情况下，您必须计算的输入存在不确定性，因为例如，很难检测到失败的链接和精确的网络速度是挥发性的。 如果成功的话，这项研究将导致算法可以处理现实世界网络中固有的不确定性。