AF: Small: New Directions in Network Design

AF：小型：网络设计的新方向

• 批准号: 2228995
• 负责人: Michael Dinitz
• 金额: $ 56.8万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-11-01 至 2025-10-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2228995&HistoricalAwards=false
• 关键词: AF; Small; New; Directions; Network

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.

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