Contemporary Issues in Network Design

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

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.