Contemporary Issues in 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.