AF: Small: New Approaches to Fundamental Problems in Network Design

在我们的现代生活中，各种各样的网络包围着我们。电信网络、道路网络、社交网络、航班连接，甚至我们电脑和手机微处理器中的电路，只是其中的几个例子。一些基本的网络问题在各种不同的环境中反复出现，需要更好的算法--更重要的是，对这些问题有更敏锐的洞察力。这些问题中的许多都是算法困难的优化问题，我们不能期望在合理的时间内得到最优解。相反，必须接受近似，目标是提供尽可能高效率的最佳保证。本项目的目标是探索解决网络设计中新旧的基本优化问题的新方法和新技术。要研究的问题包括经典的旅行商问题，找到访问网络中所有节点的最短长度的旅行的问题，以及斯坦纳树问题，该问题要求用最便宜的树连接网络中的一些终端集合。这些问题已经得到了深入的研究，但最近取得了一些令人振奋的进展。这一进展背后的两项主要技术是对“细”生成树的研究，以及在设计强舍入算法方面的进展。在这个项目中，私人投资者的目标是继续在这些方向上进行调查，希望取得进一步的突破。我们考虑的另一类问题与配置网络以处理各种和不确定的需求这一相当实际的问题有关。这一背景已经展示了美丽的数学结构和重要的实际意义的组合，该项目的目标之一是扩大此类可有效解决的网络设计问题的类别。由于这些问题的根本性质，在这些问题上的进展将立即影响该领域，推动进一步的进展。它还将产生更广泛的影响，理论上的进步将帮助和指导工业的实际改进。特别是，该项目的一部分将侧重于电信网络中最新的需求模式和能力需求模型。随着带宽需求的快速增长，以及视频和多媒体的急剧增加，需要找到更有效地利用网络资源的方法。该项目另一个具有更广泛影响的核心方面是对研究生和初级研究人员的培训和指导。

Networks, of all kinds, surround us in our modern existence. Telecommunications networks, road networks, social networks, flight connections, and even the circuits in the microprocessors in our computers and cellphones are just a few examples. Some fundamental network problems appear again and again in a variety of these settings, and better algorithms - and more importantly, keener insights - into these problems are needed. Many of these problems are algorithmically hard optimization problems, and we cannot expect optimal solutions in reasonable time. Instead, approximations must be accepted, and the aim is to provide the best possible guarantee efficiently.The goal of this project is to explore new approaches and techniques for fundamental optimization problems, both new and old, in network design. The problems to be investigated include the classical traveling salesman problem, the problem of finding a tour of minimum length visiting all the nodes in a network, and the Steiner tree problem, which asks for the cheapest tree connecting some collection of terminals within a network. These problems have been intensively studied, but recently there has been some exciting progress. Two main techniques underlying this progress are the study of "thin" spanning trees, and advances in the design of strong rounding algorithms. In this project, the PIs aim to continue investigation in these directions with the hope of further breakthroughs. Another class of problems we consider relates to the quite practical issue of provisioning a network to handle varied and uncertain demands. This context has already demonstrated a combination of beautiful mathematical structure and important practical implications, and one of the goals of this project is to expand the class of such network design problems that can be efficiently solved.Due to their fundamental nature, progress on these problems would have an immediate impact on the field, driving even further progress. There would also be a broader impact, with theoretical advancements aiding and guiding practical improvements in industry. In particular, part of the project will focus on recent models of demand patterns and capacity requirements in telecommunication networks. As bandwidth requirements increase rapidly, with the dramatic increase in video and multimedia, ways need to be found to more efficiently utilize network resources. Another central aspect of this project with broader impact is the training and mentoring of graduate students and junior researchers.