AF: Small: New Directions in Network Design

网络设计是计算机科学中的一个中心任务，它试图构建在一定约束下优化某些目标函数的图。涉及网络设计的算法问题出现在许多不同的环境中，从设计计算机网络到稀疏大数据。由于其重要性，网络设计一直是广泛研究的主题，而且已经知道了大量的信息。然而，随着技术和社会的发展，新的网络设计问题变得重要起来。这些通常是以前研究得很好的问题的变体，但需要新的模型、技术和想法。这个项目涉及研究这些新问题中的一些。特别是，这个项目包括关于利用新的可重构技术设计大规模计算机网络的问题；关于将不是网络设计问题的经典对象拿出来并通过网络设计透镜来看待它们、增加它们的实用价值的问题；以及专注于处理旧的网络设计问题并研究更灵活的变体以使其在更现代的环境中有用的问题。该项目还包括在这项工作的更多应用方面指导和纳入未被充分代表的本科生和高中生，并通过现有的基于数学的课程延伸到巴尔的摩的中学。更详细地说，该项目涉及网络设计的三个新方向，这些方向以前没有得到认真研究，但在理论和实践上都很重要。第一：以前没有应用的问题，但由于新技术的出现，现在在实际应用中非常重要，在理论上也是自然的。本项目专注于按需感知网络拓扑设计，这涉及到由网络技术的进步推动的有趣的新理论问题。第二：优化通常被认为是极端的图论对象和数据结构。特别是，这个项目包括研究几何扳手、仿真器、距离预言和光谱稀疏器的优化版本。第三，经典问题的新目标函数。这方面的主要例子是经典的网络设计问题(生成树、斯坦纳树等)。其中新的目标是次数向量的p-范数，推广和内插于总边数(1-范数)和最大次数(无穷大-范数)的经典目标之间。P-范数是算法其他部分的标准目标，但以前在网络设计中没有考虑到。研究中间规范将允许算法用户使用单个旋钮在全局密度(1范数)和局部密度(无穷范数)之间进行内插。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Network design, where one attempts to build graphs that optimize some objective function subject to some constraints, is a central task in computer science. Algorithmic problems involving network design arise in many different settings, ranging from designing computer networks to sparsifying big data. Given its importance, network design has been the subject of extensive study, and an enormous amount is already known. However, as technology and society evolve, new network design problems become important. These are often variants of previous well-studied problems but require new models, techniques, and ideas. This project involves studying some of these new problems. In particular, this project includes problems about designing large-scale computer networks that utilize new reconfigurable technologies; problems about taking classical objects that are not network-design problems and looking at them through a network design lens, increasing their practical utility; and problems that focus on taking old network design problems and studying more flexible variants to make them useful in more modern settings. This project also incorporates mentoring and including underrepresented undergraduates and high school students in the more applied aspects of this work and outreach to middle schools in Baltimore through existing mathematics-based programs.In more detail, this project involves three new directions for network design that have not previously been seriously studied but are theoretically and practically important. First: problems that previously had no application but, due to the advent of new technologies, are now extremely important in actual applications while also being theoretically natural. This project focuses on demand-aware network topology design, which involves intriguing new theoretical problems motivated by advances in networking technology. Second: optimizing graph-theoretic objects and data structures that are usually thought of as extremal. In particular, this project includes studying optimization versions of geometric spanners, emulators, distance oracles, and spectral sparsifiers. Third: new objective functions for classical problems. The main example of this is classical network design problems (spanning tree, Steiner tree, etc.) where the new objective is the p-norm of the degree vector, generalizing and interpolating between the classical objectives of the total number of edges (the 1-norm) and the maximum degree (the infinity-norm). The p-norm is a standard objective in other parts of algorithms but has not previously been considered in network design. Studying intermediate norms will allow the algorithm user to use a single knob to interpolate between global density (the 1-norm) and local density (the infinity-norm).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.